[Java] 2812 크게 만들기 - 덱(Deque)

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

2812번: 크게 만들기

[코드]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.ArrayDeque;
import java.util.Deque;
 
public class bj2812 {
    static int N;
    static int K;
    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();
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
 
        String str = br.readLine();
        Deque<Character> dq = new ArrayDeque<>();
 
        for (int i = 0; i < N; i++) {
           System.out.println(str.charAt(i));
            while(K>0 && !dq.isEmpty() && dq.getLast() < str.charAt(i)) {
                dq.removeLast();
                K--;
            }
           dq.addLast(str.charAt(i));
        }
for (int i = 0; i < dq.size(); i++){sb.append(dq.removeFirst());i--;
       }
        System.out.println(sb);
    }
}

[풀이]

맨 처음에는 내림차순으로 정렬한 후 K개만큼 가장 작은 숫자들을 리스트의 index를 유지하면서 지워나갔다.

예제 3번에서 장렬하게 틀리고 생각을 해보았다.... 뭐가 틀렸을까 싶었는데

인덱스를 유지하면서 비교해가면서 지워야겠다고 생각했다. 

dq에서 맨 뒤 원소를 지우기 위한 조건 : * 일단 덱을 한바퀴 도는 과정은 str의 원소 순서와 같이 간다.

1. 아직 원소 2개를 모두 지우지 않았어야 한다. (K 이상으로 지우면 안됨)

2. 덱이 비면 안된다. (맨 첫번째에는 뺄게 없으니)

3. 덱의 마지막 원소보다 현재 추가할 원소가 커야한다. (그래야 추가했을때 숫자가 더 커지므로)

대충 이런식으로 작동

 

그리고 마지막에 stringbuilder로 합쳐준다. 끝!