2812번 크게 만들기

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

처음 생각

문자열 s를 받아서, 내림차순 정렬을 한다. 그런 다음 n-k번만 앞에서부터 출력한다.

하지만 알고보니, '순서'를 바꿀 순 없었다. 왜 문제에는 언급이 없지?

두 번째 생각

Queue q로 접근.

예를 들어보면서 설명.

5 2

32834

라고 하자.

q에 우선 3을 넣는다.

그리고 2를 넣는다. 2가 3보다 더 작으니 무시하고, q에 2를 넣는다.

8을 넣는다. 2(q.peek())보다 8이 크니 2를 지운다. 이 때, k를 1 감소시킨다.(그렇다면, 현재 k = 1)

이때에 2를 지우려면, Deque을 써야함을 깨달았다.

세 번째 생각

Deque dq사용.

두 번째 생각에서 이어서 써보자.

현재 dq에는 [3, 8]이 있다.

3을 넣어보자면, 8보다 3이 더 작으므로, 8을 안 꺼내도 된다. 3은 그대로 대입.

dq = [3, 8, 3]

4를 넣어보자. 

dq.peekLast()(=3)이 4보다 더 작으므로, 3을 삭제. 4를 대입

그렇다면 dq에는 [3, 8, 4]가 있고, 정답은 384이다.

하지만 예외가 있는데,

6 2

654321

같은 숫자들이 내림차순일 때 k는 0으로 되지 않는다.(또는 k가 아직 0이 아닐 때)

이럴 경우 끝에서 남은 k번만큼 덜 출력해주면 된다.

첨부한 코드의 33번 째 줄 참고.

import java.io.*;
import java.util.*;
 
public class Main {
 
    static int n, k;
    static String s;
    static char[] temp;
    static Deque<Integer> dq = new LinkedList<Integer>();
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        
        st = new StringTokenizer(br.readLine());
        
        n = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());
        s = br.readLine();
 
        for(int i=0; i<n; i++) {
            
            while(k>0 && !dq.isEmpty() && dq.peekLast() < s.charAt(i) - '0') {
                dq.removeLast();
                --k;
            }
            
            dq.addLast(s.charAt(i) - '0');
        }
        
        // 만약 k가 남아있다면(오직 내림차순의 경우 등등), 끝에서 남아있는 k번 만큼 출력을 덜 해준다.
        while(!dq.isEmpty() && n-k>0) {
            bw.write(String.valueOf(dq.pollFirst()));
            ++k;
        }
        
        bw.write("\n");
        bw.flush();
        bw.close();
    }
}