2812번 크게 만들기
난이도
골드
문제 설명
https://www.acmicpc.net/problem/2812
문제
N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N과 K가 주어진다. (1 ≤ K < N ≤ 500,000)
둘째 줄에 N자리 숫자가 주어진다. 이 수는 0으로 시작하지 않는다.
출력
입력으로 주어진 숫자에서 K개를 지웠을 때 얻을 수 있는 가장 큰 수를 출력한다.
예제 입력
4 2
1924
예제 출력
94
요구사항
간단히, N자리 숫자에서 K개의 숫자를 제거했을 때, 만들 수 있는 가장 큰 수를 구하는 것이다.
규칙:
1. 주어진 숫자에서 정확히 K개의 숫자를 지운다.
2. 숫자의 원래 순서는 변경할 수 없다.
출력: K개를 지우고 남은 숫자들로 만들 수 있는 가장 큰 수.
제한: 1 ≤ K < N ≤ 500,000
접근 방식
가장 큰 수를 만들기위해 앞자리에 가장 큰 수가 와야한다는 그리디 원칙을 떠올렸다. 이를 구현하기 위해 스택을 이용하였다. 스택을 '내가 만들고 있는 가장 큰 수'라고 생각하고 아래 과정을 따랐다.
1 ≤ K < N ≤ 500,000 이기 때문에, 한번의 루프로 큰 수를 구해야 한다고 생각하였다.
숫자를 처음부터 하나씩 순회하며 스택에 담는다.
while (!stack.isEmpty() && stack.peek() < currentDigit && k > 0)만약, 현재 숫자가 스택의 맨 위에 담긴 숫자보다 크다면, 스택의 맨 위에 숫자가 크거나 스택이 빌 때까지 pop()을 실행하고 k를 1 감소한다.
while 루프가 끝나면 push()하여 스택에 채워 넣는다.
- 주의점:
만약, 98765와 같이 내림차순으로 정렬된 숫자인 경우 위와 같은 규칙을 적용한다면, pop()이 한번도 발생하지 않는다. 하지만, k번 만큼 pop()을 하여 가장 뒤의 숫자들을 삭제하면 가장 큰 수가 나온다.
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main{
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
StringBuilder sb = new StringBuilder();
int n = Integer.parseInt(st.nextToken());
int k = Integer.parseInt(st.nextToken());
String line = br.readLine();
Stack<Character> stack = new Stack<>();
for (int i = 0; i < line.length(); i++) {
if (!stack.isEmpty()) {
while (!stack.isEmpty() && stack.peek() < line.charAt(i) && k>0) {
stack.pop();
k--;
}
stack.push(line.charAt(i));
} else {
stack.push(line.charAt(i));
}
}
while (k>0){
stack.pop();
k--;
}
while (!stack.isEmpty()){
sb.append(stack.pop());
}
String answer = sb.reverse().toString();
System.out.println(answer);
}
}
느낀점
처음에는 '스택의 peek값이 현재 값보다 작으면 pop한다'는 핵심 아이디어까지는 접근하였다. 하지만, 이 검사를 if문으로 한번만 실행해야 된다고 잘못 생각하였다. '4177252841'같은 숫자가 들어왔을 때 7은 1뿐만 아니라 4까지 제거해야한다는 연쇄 반응을 놓친 것이였다. 이러한 문제를 통해 while문을 이용한 조건부 반복 제거의 중요성을 체감하였다.
솔직히, 연쇄 반응을 혼자 생각해내지 못해 마음이 조금 불편하였다. 하지만 해설을 통해 while문이라는 힌트를 얻게 나니, 전체 로직이 한번에 이해되는 경험을 하게되었다. 스택을 이용한 그리디 문제에서 '연쇄적으로 제거하여야 하는가?'라는 새로운 체크리스트를 얻게 되었다. 완벽하게 풀지는 못했지만, 결정적인 깨달음을 얻고 그것을 내것으로 만들 수 있어 성공적인 학습 과정이라고 생각한다.
