[백준/Java] 2812번 크게 만들기

문제 링크

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

2812번: 크게 만들기

접근 방법

문제 자체는 간단합니다. 1231234 에서 3개의 숫자를 뺀 가장 큰 숫자가 3234라는 것을 사람은 쉽게 생각할 수 있을        것입니다. 숫자 지우는 과정을 단계별로 살펴보겠습니다.

1231234에서 숫자를 하나빼서 만들 수 있는 가장 큰 숫자는 가장 앞의 1을 뺀 231234입니다. 다른 어느 위치의 숫자를    지워도 이 숫자보다 클 수 없습니다.

231234에서 숫자를 하나빼서 만들 수 있는 가장 큰 숫자는 앞선 이유와 동일하게 31234입니다. 마찬가지로 다른 어느 위치의 숫자를 지워도 이 숫자보다 클 수없습니다.

이제 31234에서 숫자를 하나 빼보겠습니다. 만들 수 있는 가장 큰 숫자는 2번째 자리의 1을 지운 3234입니다.                  왜 그럴까요? 앞선 이유로 3을 뺀다면 1234가 될 것이고 이는 3234보다 작습니다. 

위의 과정을 통해 알 수 있는 규칙은 i번째 숫자 앞에 i 번째 숫자 보다 작은 수가 있다면 무조건 지우는 것이 좋다는 것입니다. 

다른 예로 41772 이라는 숫자에서 2개의 숫자를 뺀 가장 큰 숫자를 구해보겠습니다.

2번째 숫자인 1 입장에서 자기 앞의 숫자인 4는 1보다 크고, 4를 지우면 오히려 숫자가 더 작아지기 때문에 4를 빼면 안될 것입니다. 다음으로 3번째 숫자인 7입장에서 자기 앞의 숫자인 1을 지우면 다른 어떤 위치의 숫자를 뺀 것 보다도 큰 숫자를 만들 수 있습니다. 앞자리의 숫자가 커질 수록 숫자가 커지기 때문입니다.

이제 4772가 되었고 남은 숫자를 지울 수 있는 횟수는 1번입니다. 아직 7 입장에서 자기 앞의 숫자 4가 자신보다 작기 때문에 이를 빼는 것이 가장 큰 수를 만들 수 있는 방법입니다. 

핵심은 i번째 숫자 앞에 i 번째 숫자 보다 작은 수가 있다면 무조건 지우는 것이 좋다는 것이 되겠습니다.

주의할 점은 내 앞의 숫자가 나보다 작은 경우가 없는 경우입니다. 예를 들어 654321과 같은 숫자가 있다면 위의 조건을 만족하는 수가 없기 때문에 어느 숫자도 지워지지 않을 수 있습니다. 하지만 문제에 따르면 반드시 K개의 숫자를 지워야하기 때문에 앞이 아닌 뒤에서부터 남은 지워야하는 숫자의 개수만큼 지우면 되겠습니다.

 

코드

import java.io.*;
import java.util.*;

public class Main {

    static int N, K, cnt;
    static Stack<Character> s = new Stack<>();
    static String number;

    public static void main(String args[]) throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        number = br.readLine();
        StringBuilder answer = new StringBuilder();
        
        for(int i = 0; i < number.length(); i++){
            while(!s.isEmpty() && cnt < K && s.peek() < number.charAt(i)) {
                cnt++;
                s.pop();
            }
            s.push(number.charAt(i));
        }
        
        for(int i = cnt; i < K; i++) s.pop();
        
        while(!s.isEmpty()) answer.append(s.pop());
        StringBuffer sb = new StringBuffer(answer.toString());
        bw.write(sb.reverse().toString());
        bw.flush();
        bw.close();
    }
}

 

코드 설명

기본적으로 위의 핵심 규칙을 구현하였고 정확히 K개 만큼 지워야하기 때문에 cnt라는 변수를 두어 지운 숫자를 세었습니다. 현재 위치에서 나보다 앞에 있는 작은 숫자를 지우는 것이므로 스택을 사용하여 push, pop 형태로 구현하는 것이 가장 편리할 것입니다. 이때 앞서말한 주의사항에 유의하여 앞선 규칙을 사용하여 K개의 숫자를 지우지 못했다면 뒤에서부터 지우는 것이 가장 큰 숫자를 만드는 방향이므로 뒤에서부터 숫자를 지웠습니다.