[Baekjoon] 2812_크게 만들기

Gold III

문제(출처: https://www.acmicpc.net/problem/2812)

---

< 크게 만들기 >

 

문제 풀이 

 

Stack을 사용해서 다음 숫자가 현재 숫자보다 크다면 현재 숫자를 stack에서 pop 해준다.

 

예를 들어 예제에서 주어진 입력이라면

4 2
1924

위의 그림과 같이 처음에 1을 stack에 넣어준다. 그다음 값이 9일 때 stack에 들어있는 값이 1 이므로 1을 빼고 9를 넣으면 더 큰 값을 만들 수 있다. 2는 9보다 작으므로 stack에 넣어준다. 마지막으로 4가 들어올 때 2보다 크므로 2를 빼주고 4를 넣어준다.

 

 

 my solution (Java)

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

public class _2812_ { // 크게 만들기

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(bf.readLine());

		int n = Integer.parseInt(st.nextToken());
		int k = Integer.parseInt(st.nextToken());

		String str = bf.readLine();
		Stack<Integer> stack = new Stack<>();

		stack.add(str.charAt(0) - '0');

		for (int i = 1; i < n; i++) {
			int num = str.charAt(i) - '0';
			while (!stack.isEmpty() && k > 0 && stack.peek() < num) {
				stack.pop();
				k -= 1;
			}
			stack.add(num);
		}

		while (k > 0) {
			k-=1;
			stack.pop();
		}

		for (int x : stack) {
			bw.write(x + "");
		}

		bw.flush();
	}
}

 

Main

변수)
n : 자릿수
k : 지울 개수
str : N자리 숫자

 

- n과 k 입력

- stack에 n자리 숫자의 첫 번째 숫자 넣기

- 다음 숫자부터 반복

: stack이 비어있지 않고 지울 개수가 남아있으며 다음 숫자가 stack에 있는 숫자보다 크다면 stack에 있는 값을 제거

: 현재 숫자 stack에 추가

- 입력받은 n자리 숫자를 순회한 후 아직 지울 개수가 남아있다면 stack에서 값 제거

- stack에 있는 값 출력

---

---