Programmers: 큰 수 만들기

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

 

떠오르는 풀이대로 손코딩을 했다. 아래 코드는 그 코드를 컴퓨터로 옮겨적은 것이다.

import java.util.*;

class Solution {
    
    private class Min {
        
        int number;
        int idx;
        
        public Min(int number, int idx) {
            this.number = number;
            this.idx = idx;
        }
    }
    
    public String solution(String number, int k) {
        
        String answer = "";
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < number.length(); i++) {
            list.add(number.charAt(i) - '0');
        }
        
        int cnt = k;
        int idx = 0;
        while (cnt != 0) {
            if (idx < list.size() - 1 && list.get(idx) < list.get(idx + 1)) {
                list.remove(idx);
                cnt--;
                if (idx != 0) {
                    idx--;
                }
                continue;
            }
            idx++;
            if (idx == list.size() - 1) {
                while (cnt > 0) {
                    Min min = new Min(list.get(0), 0);
                    for (int i = 1; i < list.size(); i++) {
                        if (list.get(i) < min.number) {
                            min = new Min(list.get(i), i);
                        }
                    }
                    list.remove(min.idx);
                    cnt--;
                }
            }
        }
        
        for (Integer i : list) {
            answer += i;
        }
    
        return answer;
    }
}

 

이 코드의 제출 결과, 10번 테스트 케이스에서 시간 초과가 났다.

 

반례를 찾아봤는데, 말그대로 효율적이지 않은 코드라서 시간 초과가 난 거라, 구글링을 시작했다. 그 결과, 이 문제의 그리디 풀이는 아래와 같다. https://ansohxxn.github.io/programmers/kit22/ 의 풀이를 참고했다.

 

 

구현은 다음과 같이 했다.

import java.util.*;

class Solution {
    
    public String solution(String number, int k) {
        
        String answer = "";
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < number.length(); i++) {
            list.add(number.charAt(i) - '0');
        }
        
        int idx = 0;
        for (int i = k; i < list.size(); i++) {
            int max = 0;
            for (int j = idx; j <= i; j++) {
                if (list.get(j) > max) {
                    max = list.get(j);
                    idx = j + 1;
                    if (max == 9) {
                        break;
                    }
                }
            }
            answer += max;
        }
        
        return answer;
    }
}

 

채점 결과, 모든 테스트 케이스를 통과했다.