https://www.acmicpc.net/problem/2812
N자리 숫자에서 K개를 지워 얻을 수 있는 가장 큰수를 구하는 문제이다.
접근 방법을 모색하기 위해 먼저 주어진 예제들을 분석해 보았다.
예제 1,2번만 보면 앞에서부터 순회하며 다음 숫자가 더 크면 이전 숫자를 제외하는 것인가? 생각이 들었다.
하지만 3번에서 스택을 사용하는 문제란걸 느꼈다.
4177252841이라는 숫자에서 숫자를 제외한다면, 다음 자릿수의 수가 현재 자릿수의 수보다 크다면 이전 자릿수들을 역행하며 다음 자릿수보다 작다면 제외해야 한다.
예를 들어 4177252841에서 3개를 제외한다고 해보자.
자릿수 4의 위치에서, 다음 자릿수인 1은 현재보다 크지 않다. 따라서 아직 제외하지 않는다. (스택에 넣는다)
자릿수 1의 위치에서, 다음 자릿수인 7은 현재보다 크다. 따라서 현재 위치부터 앞으로 가며 7보다 작은 숫자인 1과 4를 제외하게 된다.
아직 제외할 숫자가 하나 남았으므로 계속 진행한다.
자릿수 7(첫번째)의 위치에서, 다음 자릿수인 7은 현재보다 크지 않다. 따라서 아직 제외하지 않는다.
자릿수 7(두번째)의 위치에서, 다음 자릿수인 2는 현재보다 크지 않다. 따라서 아직 제외하지 않는다.
자릿수 2(첫번째)의 위치에서, 다음 자릿수인 5는 현재보다 크다. 따라서 현재 위치인 2를 제외하고 7752841을 반환한다.
알고리즘은 위와 같다. 스택을 사용하는 이유는 다음 숫자가 더 큰 경우 해당 위치에서 역방향으로 이동해야 하는데, 이때 유용하기 때문이다.
그럼 스택을 이용하는 방법으로 알고리즘 순서를 작성해 보자.
- 숫자를 입력받아 각 자릿수를 순회한다.
- 스택이 비었거나 스택 맨 위 숫자가 현재 자릿수보다 크거나 같다면 현재 자릿수를 스택에 넣는다.
- 그렇지 않고 제외할 숫자가 0이 아니고, 스택이 비어있지 않으며 스택 맨 위 숫자가 현재 자릿수보다 작은 경우 반복해 숫자를 빼낸다.
숫자를 빼낸 뒤, 현재 자릿수를 스택에 넣는다. - k가 0이 된 경우, 위 작업을 무시하고 현재 자릿수의 숫자를 스택에 넣는다.
- 위 과정을 진행한 뒤에도 k가 0이 아니면 0이 될때까지 스택을 pop한다 << 이 과정을 깜빡했다가 틀리고 나서 4177777777을 넣어보고 알았다.
- StringBuilder를 통해 스택에서 자릿수들을 꺼내 이어붙인 후 뒤집어 출력한다.
fun main(args: Array<String>): Unit = with(System.`in`.bufferedReader()) {
val (N, K) = readLine().split(' ').map{it.toInt()}
val num = readLine().toCharArray().map{it.digitToInt()}.toTypedArray()
val stack = Stack<Int>()
var k = K
for(n in num){
if(k == 0) {
stack.push(n)
continue
}
if(stack.isEmpty() || stack.peek() >= n) {
stack.push(n)
} else{
while(k > 0 && stack.isNotEmpty() && stack.peek() < n){
stack.pop()
k--
}
stack.push(n)
}
}
if(k > 0){
while(k > 0){
stack.pop()
k--
}
}
val ans = StringBuilder()
while(stack.isNotEmpty()){
ans.append(stack.pop())
}
print(ans.reverse().toString())
}