[프로그래머스/Java] 42883 큰 수 만들기

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

프로그래머스

🔍  해결 과정

문자열 number를 구성하는 숫자들 중 k개를 선택 후 제거하면서 가장 큰 수를 찾아나가면 될 것 같지만 number의 길이는 최대 100만이므로 조합의 경우는 쓸 수가 없습니다.

그래서 다른 방식으로 문제를 접근해야 하는데 어떻게 접근을 해야하는지 고찰하는 중 스택을 활용해야겠다는 생각을 하게 되었습니다. 문제 예시에 있는 number = "4177252841", k = 4를 바탕으로 고찰 과정을 설명하면 다음과 같습니다.

1️⃣ 앞자리로 갈수록 최대한 큰 수가 와야한다.
2️⃣ 스택을 하나 만들어준다. 여기서 스택은 StringBuilder 자료형을 활용하였다.
3️⃣ 처음에 스택에는 아무것도 없으므로 number의 맨 앞자리 4를 넣어준다. (스택: [4], k = 4)
4️⃣ number의 두 번째 자리 1과 스택에 있는 4를 살펴본다. 여기서 1이 4보다 작으므로 숫자 4가 앞자리를 유지해야 한다. 따라서 1을 스택에 넣어준다. (스택: [1, 4], k = 4)
5️⃣ 다음으로 number의 세 번째 자리 7을 살펴보았을 때 스택에 있는 숫자들과 크기 비교를 한다. 전부 1, 4보다 7이 크므로 스택에 있는 1, 4를 제거해준다. k = 4의 남은 횟수 중 2개를 쓰게 된다. (스택: [7], k = 2)
6️⃣ 다음 7을 살펴보았을 때 현재 스택 7과 값이 같으므로 스택에 넣어둔다. (스택: [7, 7], k = 2)
7️⃣ 위와 같은 방식으로 number의 맨 마지막 자리까지 다 살펴보았을 때 스택에 남는 최종적인 값들은 [7, 7, 5, 8, 4, 1]이 된다.
8️⃣ 스택에 남아 있는 내용들 그대로 문자열로 만들어서 반환해준다.

 

---

✏️ 코드

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

        return answer.substring(0, answer.length() - k); // k를 다 쓰지 않는 상황을 고려
    }
}