[Java] BOJ2812, 백준 - 크게 만들기

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

2812번: 크게 만들기

 

문제도 단순하고, 난이도에 비해서 쉽게 푼 것 같다.

 

풀이

N자리 숫자가 주어졌을 때 가장 큰 수를 만들려면 앞자리 숫자를 가장 크게 만들어야 할 것이다.

그러면 앞에 숫자부터 비교해서

 

1. 다음자리 숫자가 나보다 큰 경우 && 아직 제거해야할 자릿수가 남은 경우

나를 지우고 다음숫자를 이어붙여준다.

(1) 예를 들어 476127과 같은 경우 4 < 7이므로 4를 제거해야 함

(2) 76127 에서는 1 < 2 이므로 1을 제거

(3) 7627 에서는 2<7이므로 2를 제거

(4) 767 에서는 6<7이므로 6을 제거

while (!stack.isEmpty() && cnt < k) {
	if (stack.peek() >= c)
		break;
	// 전이 더 작으면 전에거를 제거
	stack.pop();
	cnt++;
}

 

2. 다음자리 숫자가 나보다 작은 경우

그냥 이어붙여준다.

 

만약 끝까지 진행했는데 아직 지워야 할 자릿수가 남은 경우
예를 들면 위의 예시에서는 77, 또는
8877554321 과 같이 구성된 경우일 것이다.

(이럴 경우 문자열은 내림차순이 됨)
그러면 가장 작은 자릿수부터 제거해준다.
이를 코드로 구현해주기만 하면 된다.

// 문자열이 끝났는데 아직 지워야 할 수가 남아있으면 끝부터 지워준다.
while (cnt < k) {
	stack.pop();
	cnt++;
}

 

시간복잡도를 머리로 계산했을때는
O(N+K)가 나오는데 혹시 오류가 있다면 지적바람

 

소스코드

import java.io.*;
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());
		int n = Integer.parseInt(st.nextToken());
		int k = Integer.parseInt(st.nextToken());
		String s = br.readLine();

		Stack<Character> stack = new Stack<>();
		stack.push(s.charAt(0));
		int cnt = 0;

		for (int i = 1; i < n; i++) {
			char c = s.charAt(i);

			while (!stack.isEmpty() && cnt < k) {
				if (stack.peek() >= c)
					break;
				// 전이 더 작으면 전에거를 제거
				stack.pop();
				cnt++;
			}
			// 아니면 그냥 이어붙여줌
			stack.push(c);
		}

		// 문자열이 끝났는데 아직 지워야 할 수가 남아있으면 끝부터 지워준다.
		while (cnt < k) {
			stack.pop();
			cnt++;
		}

		// 스택을 역순으로 출력해주면 끝
		StringBuilder sb = new StringBuilder();
		while (!stack.isEmpty())
			sb.append(stack.pop());
		System.out.println(sb.reverse());
	}
}