[JAVA 알고리즘]BAEKJOON 2812번 크게 만들기

크게 만들기

---

문제 설명

N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 K가 주어진다. (1 ≤ K < N ≤ 500,000)

둘째 줄에 N자리 숫자가 주어진다. 이 수는 0으로 시작하지 않는다.

출력

입력으로 주어진 숫자에서 K개를 지웠을 때 얻을 수 있는 가장 큰 수를 출력한다.

제한사항

• 없음

입출력 예

input	return
4 2 1924	94
7 3 1231234	3234
10 4 4177252841	775841
추가 반례
11 9 99912349111	99

---

문제 분석

N자리의 숫자와 K개의 숫자를 제거해 가장 큰 수를 만들어야 한다.

문제를 통해 알 수 있는 조건

• K개의 숫자를 제거해야 한다.
• 최종 숫자의 길이는 N - K이다.
• 순서는 변경할 수 없고, 앞자리 수일수록 큰 수가 들어가야 한다.
  • 앞에서 확인을 했을 때, K개안에서 큰 수보다 작은 수는 삭제해도 된다. 

최종 숫자의 길이를 알기 때문에 만들어지는 숫자를 앞자리부터 올 수 있는 가장 큰 수를 뽑으면서 수를 만들 수 있다.

• 최종 숫자의 길이의 배열을 모든 수를 0으로 넣어 가장 작은 수로 채워준다.
• 주어진 숫자의 앞자리 부터 삭제 가능한 개수까지의 숫자를 확인하면서 가장 큰 수의 위치를 확인하고 해당 수를 최종 숫자의 앞자리에 넣어준다.
• 가장 큰 수의 위치만큼 지나온 숫자만큼 삭제 가능한 개수를 차감시킨다.
• 최종 숫자의 다음 앞자리는 이전의 가장 큰 수의 다음 위치부터 삭제 가능한 개수까지 반복을 해준다.

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

public class Main {
   
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());
        // 숫자의 길이
        int N = Integer.parseInt(stringTokenizer.nextToken());
        // 삭제하는 숫자의 개수
        int K = Integer.parseInt(stringTokenizer.nextToken());
        // 삭제된 숫자의 길이
        int length = N - K;

        char[] num = bufferedReader.readLine().toCharArray();
        char[] result = new char[length];
        Arrays.fill(result, '0');
        // 삭제하는 시작위치
        int curIdx = 0;
        // 만드는 숫자 범위 만큼 반복
        for (int i = 0; i < length; i++) {
            // 넘어간 위치와 비교하기 위해 위치 확인
            int preIdx = curIdx;
            // 넘어간 위치에서 삭제 가능한 개수 만큼 반복
            for (int j = preIdx; j <= preIdx + K; j++) {
                if (result[i] < num[j]) {
                    result[i] = num[j];
                    curIdx = j + 1;
                }
            }
            // 앞의 숫자를 삭제 시킨 만큼 삭제한 개수를 차감
            if (preIdx != curIdx && K > 0) {
                K -= curIdx - preIdx - 1;
            }
        }

        StringBuilder stringBuilder = new StringBuilder();
        for (char c : result) {
            stringBuilder.append(c);
        }
        System.out.println(stringBuilder);
    }
}

문제 발생

시간초과가 발생한다.

반복을 할 때, 앞자리에 가장 큰 수가 왔더라도 뒤에 오는 숫자에 더 큰 수가 있는지를 알 수 없기 때문에 삭제 가능한 개수만큼 반복을 해야 된다. 그렇게 될 경우, N과 K의 범위가 500,000이기 때문에 삭제하지 못하고 계속 반복해야 하는 (N-K) K개이상의 반복 횟수로 인해 시간초과가 발생할 수 있다. (N이 500,000 K가 400,000이면 40,000,000,000번가량 반복을 할 수가 있다.)

반복 횟수를 줄일 수 있는 방법을 찾아봤을 때, 해당 자리에 숫자를 들어올 수 있는 이후의 숫자들에서 찾는 것이 아닌 숫자를 먼저 넣고 넣은 숫자들과 다음 들어올 숫자와 비교해서 작은 수를 삭제하게 되면 최대 N번만큼 넣고 K번만큼 삭제하는 경우로 매우 반복 횟수가 단축이 된다.

LILO방식이 가능한 스택 혹은 덱을 이용해서 문제를 해결할 수 있다.

수정 문제풀이

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());
        // 숫자의 길이
        int N = Integer.parseInt(stringTokenizer.nextToken());
        // 삭제하는 숫자의 개수
        int K = Integer.parseInt(stringTokenizer.nextToken());
        // 삭제된 숫자의 길이
        int length = N - K;

        char[] num = bufferedReader.readLine().toCharArray();
        LinkedList<Character> list = new LinkedList<>();
        for (int i = 0; i < N; i++) {
            // 숫자를 반복을 하면서 리스트에 숫자를 넣고 다음 숫자와 리스트의 뒷자리 부터 비교해서 작은 경우 삭제하고 삭제하는 개수를 차감해준다.
            while (!list.isEmpty() && K2 > 0 && list.peekLast() < num[i]) {
                list.pollLast();
                K2--;
            }
            list.add(num[i]);
        }

        // 삭제되는 숫자가 해당 숫자에서 가장 큰 경우와 뒤에 오는 숫자가 계속 작아질 경우 더해지기만 한다.
        // 마지막에 만들어야 하는 숫자 길이보다 긴 숫자들을 삭제처리 해줘야한다.
        while (length < list.size()) {
            list.pollLast();
        }

        StringBuilder stringBuilder = new StringBuilder();
        for (char c : list) {
            stringBuilder.append(c);
        }
        System.out.println(stringBuilder);
    }
}

그리드 알고리즘이 먼가 감이 잡힐 것 같으면서도 좀처럼 빨리 풀리지가 않는다. 문제를 푸는 시간을 줄여야 하는데, 먼가 풀릴 것 같으면서도 안 풀리니 답답한 느낌이 있다. 좀 더 공부하는 느낌으로 문제를 효율적이게 푸는 방법으로 다시 그리드 알고리즘을 정리를 해봐야겠다.

---

알고리즘 분류

• 자료 구조
• 그리디 알고리즘
• 스택

문제 출처 - https://www.acmicpc.net/problem/2812

2812번: 크게 만들기