백준/2812/Java - 크게 만들기

문제

https://www.acmicpc.net/problem/2812

2812번: 크게 만들기

---

N자리 숫자 중 숫자 K개를 지워서 가장 큰 수를 만드는 문제.

 

N-K자리의 가장 큰 수를 만들어야 하기 때문에 두 가지를 생각해야 한다.

1. 앞자리 수일수록 큰 수가 들어가야 한다.

2. 주어진 숫자들을 맘대로 재배치 하는 것이 아니라 지우는 것이므로 숫자의 순서는 지켜야 한다.

 

배열과 스택을 활용하면 위의 두 가지를 만족할 수 있다. 

스택에 가장 아래에 있는 수가 가장 큰 자리의 수라고 생각하면 간단하다. 

 

1. 먼저 N자리 숫자를 받아 배열을 만든다.

2. 스택이 비어있다면 배열의 i번째 수는 바로 스택에 넣으면 된다. (ex : 배열의 0번 인덱스)

3. (스택이 비어있지 않을 때) 배열의 i번째 숫자가 스택의 최상단보다 크다면,  해당 자리수는 배열의 i번째 수로 바뀌어야 한다. 따라서 스택 최상단의 수가 배열의 i번째 숫자보다 크지 않을 때 까지 제거 한 뒤, 배열의 i 번째 수를 스택에 넣어준다.

4. 단, K개를 초과하여 숫자를 지워선 안된다.

 

이러한 조건을 만족하는 반복문은 다음과 같다.

for(int i=0; i<N; i++) {
    while(!stack.isEmpty() && stack.peek() < arr[i] - '0' && popCount < K) {
        stack.pop();
        popCount++; 
    }
    stack.push(arr[i] - '0');
}

 

그러나  위의 반복문은 K만큼 stack에서 pop을 하지 않는 경우가 발생한다.

숫자를 K개 지워야 하는데 그만큼 지우지 않아 정답보다 자리수가 커지게 된다.

/* 반례 입력
10 5
9993333932

정답 : 99993
출력 : 999932
*/

K만큼 stack에서 pop을 하지 않는 경우는 결국, K개를 지우지 못했는데 배열이 내림차순으로 끝났다는 것을 의미하므로

popCount가 K가 될 때까지 스택의 최상단을 제거해주면 된다.

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));		
		StringBuilder sb = new StringBuilder();
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int N = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());
		
		String s = br.readLine();
		char[] arr = s.toCharArray();
		Stack<Integer> stack = new Stack<>();
		int popCount = 0;
		
		for(int i=0; i<N; i++) {
			while(!stack.isEmpty() && stack.peek() < arr[i] - '0' && popCount < K) {
				stack.pop();
				popCount++;
			}
			stack.push(arr[i] - '0');
		}
		
		while(popCount < K) {
			stack.pop();
			popCount++;
		}
		for(int val : stack) {
			sb.append(val);
		}
		System.out.println(sb);
	}
}