2812번 : 크게 만들기 [JAVA]

문제링크

성공 여부(걸린 시간): 성공(43분)

아이디어

이 문제는 길이가 N인 수에서 K개의 숫자를 제거해 가장 큰 수를 만드는 문제이다. 핵심은 앞에서부터 가능한 한 큰 숫자를 남기기 위해 작은 숫자를 우선적으로 제거하는 것이다.

먼저 입력받은 숫자를 큐에 차례대로 저장한다. 결과를 담을 자료구조로는 스택처럼 동작할 수 있는 Deque를 사용한다.

숫자를 앞에서부터 하나씩 확인하면서, 현재 숫자가 다음 숫자보다 크거나 같다면 결과에 넣는다. 하지만 현재 숫자가 다음 숫자보다 작다면 뒤에 더 큰 숫자가 있다는 의미이므로 현재 숫자를 제거하고 K를 하나 줄인다. 이 과정을 K가 0이 되거나 큐가 빌 때까지 반복한다.

그 후 큐에 남은 숫자들을 결과에 넣어주고, 만약 아직 K를 다 쓰지 못했다면 이는 이미 앞부분이 모두 내림차순이 된 경우이므로 뒤에서부터 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 num = br.readLine();
        if(N+K==2){
            System.out.print(0);
            return;
        }
        ArrayDeque<Integer> q = new ArrayDeque<>();//뽑아서 하나씩 확인할 큐
        ArrayDeque<Integer> result = new ArrayDeque<>();//결과로 출력할 스택

        for(char x: num.toCharArray()){
            q.add(x-'0');
        }

        while (K!=0&&!q.isEmpty()){
            int cur = q.poll();
            if(q.isEmpty()){
                result.add(cur);
                break;
            }
            if(cur>=q.peekFirst()){
                result.add(cur);
            }
            else {
                while(--K!=0&&!result.isEmpty()&&result.peekLast()<q.peekFirst()){
                    result.pollLast();
                }
            }
        }
        while (!q.isEmpty()){//q에 남은거 result에 넣어주기
            result.add(q.poll());
        }
        for(int i=0; i<K; i++){//K가 0이 안되었는데 끝났다-> 전부 왼큰수가 되었다면 뒤에서부터 남은 K 횟수만큼 pollLast 해줌
            result.pollLast();
        }
        for(int x:result){
            System.out.print(x);
        }
    }
}