[프로그래머스] 큰 수 만들기(Java, Greedy, Lv2, 새로운 코드, 사고력)

programmers.co.kr/learn/courses/30/lessons/42883#

코딩테스트 연습 - 큰 수 만들기

 

## 접근방법

---

주어진 문자열에서, K개만큼을 지워서 가장 큰 수를 만들어야 한다. 앞자리가 클수록 가장 큰 수에 가까워질 것이다.

 

 

 

그렇다면, 어떻게 앞자리를 크게 만들까? 앞에서 탐색하면서, 해당 수보다 큰 수가 존재한다면 그 수로 교체할 수 있다. 그 수로 교체하기 위해선 사이에 있는 수들은 모두 지워야 한다. 만약에 사이에 있는 수들을 모두 지웠는데 정답의 길이가 되지 않는다면, 찾은 큰 수를 선택할 수 없다.

 

 

 

매순간에 앞자리를 크게 만드는 것이 가장 큰 수를 만들 수 있는 방법이다.

 

 

 

어떤 수보다 큰 수의 후보들은 (해당 수 + 1 ~ 9)가 될 것이다. 뒤에 위치한 나머지 수들을 확인하면서 가장 큰 수를 찾는 것은 시간복잡도가 O(N * N)으로 커지게 된다. N은 1,000,000이므로 시간 초과가 발생할 수도 있다. 

 

 

 

구글링을 통해서 다른 풀이들을 보면, O(N * N)으로 풀었는데도 시간 초과가 나진 않긴 한다. 하지만 좀 더 확장성이랑 실력을 키우기 위해 시간복잡도를 고려해보자.

 

 

 

O(N)의 스캔으로 0 ~ 9부터의 모든 숫자들의 위치를 리스트 자료구조를 이용해서 기억해놓을 수 있다. 자료구조에 해당 값들을 저장해두면, 자기보다 큰 수들의 위치만 확인할 수 있게 된다. 모든 수들의 위치의 수는 O(N)과 동일하며, 0 ~ 9는 상수이다, 따라서 시간복잡도 O(N)만에 문제를 해결할 수 있다.

 

 

 

또한 특정 숫자의 위치를 기억한 자료구조의 인덱스를 저장하고 있는 배열을 통해서, 매번 자료 구조를 풀 스캔하는 것이 아니라, 탐색이 끝난 위치 이후부터 다시 시작할 수 있도록 해야 한다.

 

 

## 해설코드

---

import java.util.*;
 
class Solution {
    public String solution(String number, int k) {
        StringBuilder sb = new StringBuilder("");
        int target = number.length() - k;
        
        List<Integer>[] list = new List[10];
        int[] idx = new int[10];
        
        for(int i = 0; i < list.length; i++)
            list[i] = new ArrayList<>();
        
        for(int i = 0; i < number.length(); i++){
            int num = number.charAt(i) - '0';
            list[num].add(i);
        }
        
        for(int i = 0; i < number.length(); i++){
            int num = number.charAt(i) - '0';
            
            for(int j = 9; j >= num + 1; j--){
                if(list[j].size() == 0) continue;
                
                while(idx[j] < list[j].size() && list[j].get(idx[j]) <= i)
                    idx[j]++;
                
                if(list[j].size() == idx[j]) continue;
                
                if(list[j].get(idx[j]) - i <= k){
                    k -= (list[j].get(idx[j]) - i);
                    i += (list[j].get(idx[j]) - i);
                    break;
                }
            }
            
            sb.append(number.charAt(i));
            if(sb.length() == target) break;
        }
        
        return sb.toString();
    }
}