[프로그래머스 알고리즘 고득점 Kit][그리디][Java] 큰 수 만들기

https://school.programmers.co.kr/learn/courses/30/lessons/42883

프로그래머스

 

큰 수는 앞자리 숫자가 클수록 유리하므로 StringBuilder를 스택처럼 사용한다.

숫자를 왼쪽부터 확인
→ 현재 숫자가 저장된 마지막 숫자보다 크면 마지막 숫자 삭제
→ 삭제 횟수가 k가 되거나 더 이상 작은 숫자가 없을 때까지 반복
→ 현재 숫자 추가

 

 

다음 숫자가 더 클 때만 삭제하므로

오름차순인 경우는 삭제 횟수가 남을 수 있음 

그래서 모든 숫자를 순회하고도 삭제 횟수가 남았다면 뒤에서부터 삭제를 해야함

 

 

 

각 숫자는 한 번 추가되고 최대 한 번 삭제됨 : 시간 복잡도: O(N)

 

class Solution {
    public String solution(String number, int k) {
        StringBuilder sb = new StringBuilder();
        
        char first = number.charAt(0);
        sb.append(first);
        int count = 0;
        
        for(int i=1; i<number.length(); i++) {
            while(count < k && sb.length() > 0 && sb.charAt(sb.length() - 1) < number.charAt(i)) {
                sb.deleteCharAt(sb.length() - 1);
                count++;
            }
            
            sb.append(number.charAt(i));
        }
        
        for(int i=count; i<k; i++) {
            sb.deleteCharAt(sb.length() - 1);
        }
        
        return sb.toString();
    }
}