[백준] 2812번: 크게 만들기 - java

 

 

 

나의 풀이 - deque

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

public class Main {

	static BufferedReader br;
	static BufferedWriter bw;
	static StringBuilder sb;
	static StringTokenizer st;
	static int n, k;
	static ArrayDeque<Character> deque;

	public static void main(String[] args) throws IOException {
		br = new BufferedReader(new InputStreamReader(System.in));
		bw = new BufferedWriter(new OutputStreamWriter(System.out));
		sb = new StringBuilder();
		st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		k = Integer.parseInt(st.nextToken());
		char[] input = br.readLine().toCharArray();
		deque = new ArrayDeque<Character>(); // 현재 원소와 비교하기 위한 현재원소보다 앞에 위치한 숫자들

		for (int i = 0; i < input.length; i++) {
        		// k개를 아직 지우지 않았고, 덱이 비어있지 않고, 덱의 마지막 원소보다 현재원소가 더 크다면
			while (k > 0 && !deque.isEmpty() && deque.peekLast() < input[i]) {
				deque.pollLast(); // 덱의 마지막 원소를 제거한다.
				k--; // 지워야할 k 개수 감소
			}
			deque.addLast(input[i]); // 덱에 현재 원소를 추가한다.
		}

		// deque 의 앞에서부터 제거한다. k개를 다 제거하지 못한 경우에는, 뒤에 있는 숫자들을 버린다.
		while (deque.size() > k) 
			sb.append(deque.pollFirst());
		System.out.println(sb.toString());
	}
}

 

아이디어 : 현재 수보다 작은 수가 앞에 있는 경우, 앞에 있는 숫자를 지운다. 앞 자릿수에 큰 숫자가 와야 한다!

=> 맨 앞자리수가 클수록 숫자는 커진다.

=> 앞자리부터 순차적으로 수를 하나씩 검사하며, 앞자리 수를 가능한 크게 만드는 선에서 k개의 숫자를 제외시킨다.

 

 

Deque 사용 => Deque 에는 현재원소 앞에 있는 숫자들이 들어있다. 따라서 현재원소와 deque 의 마지막 원소를 비교하며, deque 의 마지막 원소가 현재원소보다 작다면 제거한다.

* Deque 사용 이유 : 제거할 때는 마지막 원소부터 제거해야 하고, 출력할 때는 앞에서부터 순서대로 출력해야 하므로,

맨앞/뒤에서 삽입,제거가 가능한 Deque 을 사용하였다.

 

0~n-1번 인덱스까지 앞에서부터 순차적으로 탐색한다.

1. (반복) 덱이 비어있지 않을 경우, 덱의 맨 끝과 현재원소를 비교를 한다. => 현재원소보다 앞에 있으면서 작은 원소 제거하는 과정

• 덱의 맨 끝이 현재원소보다 더 작을 경우 덱에서 없애고, k--. 반복해서 비교해본다.
• 그렇지 않을 경우 반복문 탈출

2. 현재 원소를 맨 끝에 집어 넣는다.

 

- k개의 숫자가 이미 지워졌는데, 아직 숫자가 남은 경우: 남은 숫자들은 뒤에 붙힌다.
- 모든 자리를 전부 탐색했는데 k개를 못 지운 경우: 이미 큰 숫자들이 앞에 있는 경우이므로, 가장 늦게 들어온 k개를 지운다.

 

 

ex)

4177252841