https://school.programmers.co.kr/learn/courses/30/lessons/42883
문제 설명
어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하려 합니다.
예를 들어, 숫자 1924에서 수 두 개를 제거하면 [19, 12, 14, 92, 94, 24] 를 만들 수 있습니다. 이 중 가장 큰 숫자는 94 입니다. 문자열 형식으로 숫자 number와 제거할 수의 개수 k가 solution 함수의 매개변수로 주어집니다. number에서 k 개의 수를 제거했을 때 만들 수 있는 수 중 가장 큰 숫자를 문자열 형태로 return 하도록 solution 함수를 완성하세요.
제한 조건
- number는 2자리 이상, 1,000,000자리 이하인 숫자입니다.
- k는 1 이상 number의 자릿수 미만인 자연수입니다.
풀이 과정
가장 큰 수를 만들기 위해서는 가장 큰 자리수에 9혹은 9와 가까운 숫자가 들어가야합니다. 숫자의 위치는 서로 바뀌지 않으며 String에서 k만큼의 Character만 제거하면 되므로 앞에서부터 오른쪽 숫자와 비교하여 작은 수를 하나씩 빼가면 됩니다.
저는 비교하는 과정에서 스택을 사용하여 가장 최신 숫자(왼쪽에 있는 숫자 중에 현재 인덱스와 가까운 숫자)와 비교할 수 있도록 했습니다.
- 문자열의 모든 문자를 순회할 것이다.
- 앞에서부터 사용할 문자는 스택에 저장한다.
- 스택이 비어있지 않으면 스택의 가장 위에 있는 문자(문자열에서는 현재 인덱스보다 왼쪽에 있는 문자)를 가져와 현재 인덱스 문자와 비교합니다.
- 왼쪽에 있는 문자가 현재 인덱스 문자보다 적을 경우 스택에서 제거합니다.
- 이미 k만큼 문자를 제거했다면 모든 문자를 스택에 추가합니다.
- 스택에 저장되어있는 문자를 StringBuilder 를 사용해 문자열로 만들어줍니다.
- 스택은 기존 문자열의 역순으로 반환되므로 StringBuilder의 내용을 뒤집습니다.
- 뒤집은 문자열에서 빼야하는 남은 문자를 제외한 0~(문자열길이-k(남은 제거 문자 개수))를 뽑아 반환합니다.
Java 코드
public String solution(String number, int k) {
StringBuilder sb = new StringBuilder();
Stack<Character> stack = new Stack<>();
for(int i=0; i<number.length(); i++) {
char c = number.charAt(i);
while (!stack.isEmpty() && stack.peek() < c && k > 0) {
stack.pop();
k--;
}
stack.push(c);
}
while(!stack.isEmpty()) {
sb.append(stack.pop());
}
return sb.reverse().substring(0, sb.length()-k);
}
사실 6번과정이 없이 테스트를 진행했으나 프로그래머스에 제출하니 마지막12번이 오류가 발생해서 테스트케이스를 찾아보니 아래와 같은 케이스가 있어서 수정하였습니다.
- number = 9876543214
- k = 4
.substring(0, sb.length()-k); 대신 toString() 으로 작성해서 테스트를 하니 결과가 9876544가 반환되었습니다. 기대 결과값은 987654가 나와야하는데 왜일까 디버깅을 해보니 3번을 진행하는 과정에서 같은 숫자에 대한 것은 비교하지 않는 것이였습니다. 그러나 같은 숫자라고 무조건 제외한다면 9999처럼 높은 숫자가 연속적으로 있는 경우도 모두 제거가 되어 원하는 결과가 나오지 않을 것이라고 예상했습니다.
같은 숫자 반복으로 인해 문자가 k만큼 제거되지 않는 경우는 뒤에 더 이상 해당 숫자보다 더 크거나 작은 숫자가 없을 경우입니다. 그러므로 모든 문자를 스택에 저장하여 일단 문자열을 생성한 뒤 남은 제거 숫자만큼 뒤에 문자열을 잘라줘야겠다고 생각하여 6번 과정을 추가하게 되었습니다.