막 공부를 시작한 초보 개발자

업데이트:

문제 링크

백준 2812번 - 크게 만들기 (Gold 3)

문제 설명

0으로 시작하지 않는 N자리 숫자가 주어진다.
숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하시오.

정답 코드 및 설명

가장 큰 수를 만들기 위해서는 앞자리의 값을 최대한 크게 만들어야 한다.
따라서 다음 과정을 반복하면 된다.

정답 알고리즘

  1. 앞에서부터 (K + 1)개의 숫자 중 가장 큰 숫자를 택한다.
    • 가장 큰 숫자가 여럿이라면, 그 중 가장 앞 숫자를 택한다.
  2. 1에서 보기 시작한 위치부터 2에서 택한 숫자의 앞까지를 전부 지운다.
  3. K에 K - (3에서 지운 숫자의 개수)를 넣는다.
  4. 2에서 택한 다음자리의 숫자를 시작으로, 1 ~ 4를 K가 0이 될 때까지 반복한다.
  5. 남은 숫자들을 출력한다.

예를 들어 N = 10, K = 4이고 처음 주어진 숫자가 4177252841이라고 하자.

  1. 앞에서부터 5개의 숫자 중 가장 큰 숫자를 택한다 : 4, 1, 7, 7, 2 중 7이 가장 크다.
  2. 가장 큰 숫자 7이 두개이므로, 앞쪽의 7을 택한다.
  3. 처음부터 2에서 택한 7까지 2개의 숫자를 지운다 : 77252841이 남는다.
  4. K = 4 - 2 = 2로 바꾼다.
  5. 처음 숫자의 4번째 자리의 7부터 3개의 숫자 중 가장 큰 숫자를 택한다 : 7, 2, 5 중 7이 가장 크다.
  6. 맨 앞의 숫자를 택했으므로 지울 숫자는 없고, K는 여전히 2이다.
  7. 처음 숫자의 5번째 자리의 2부터 3개의 숫자 중 가장 큰 숫자를 택한다 : 2, 5, 2 중 5가 가장 크다.
  8. 2를 지운다 : 7752841이 남는다.
  9. K = 2 - 1 = 1로 바꾼다.
  10. 처음 숫자의 7번째 자리의 2부터 2개의 숫자 중 가장 큰 숫자를 택한다 : 2, 8 중 8이 가장 크다.
  11. 2를 지운다 : 775841이 남는다.
  12. K = 1 - 1 = 0으로 바꾼다.
  13. K = 0이므로 남은 775841을 출력한다.

실제 구현

위의 과정을 코드로 단순하게 구현하는 것은 효율적이지 못하다.
가능한 자릿수는 0에서부터 9까지의 총 10가지 뿐이라는 정보를 활용하지 못하고 있기 때문이다.
이를 활용하기 위해 실제 구현에서는 아래와 같은 로직을 사용하였다.

N개의 수에서 K개의 수를 제거하고 나면 M = N - K개의 수가 남는다.
따라서, 정답 알고리즘은 다음과 같이 변형이 가능하다.

  1. K > 0인 경우
    1. 현재 위치부터 시작하여 (K + 1) 개의 숫자 중 가장 크면서 가장 먼저 나오는 수를 택한다.
    2. K에 K - (1에서 택한 수의 위치 - 현재 위치)를 넣는다.
  2. K = 0인 경우 현재 위치의 숫자를 택한다.
  3. 현재 위치를 1에서 택한 수의 위치 바로 다음으로 옮긴다.
  4. 위의 과정을 M번 반복한다.

이제 1번 과정을 가능한 자릿수가 총 10가지 뿐이라는 정보를 활용해서 효율적으로 바꿔보자. 먼저, 처음 주어진 숫자를 맨 앞자리부터 훑어, 큐 index[i]에 처음 주어진 숫자에서 i가 나오는 index를 작은 값부터 순서대로 저장한다. (코드의 18 ~ 23행 참조)

위의 전처리 과정을 거치면 1번 과정을 아래와 같이 바꿔서 수행할 수 있다.

i = 9부터 시작하여 i = 0까지 i를 1씩 감소시키면서 아래의 과정을 반복한다.

  1. index[i]가 비어있으면 다음 i로 넘어간다.
  2. index[i]가 비어있지 않다면, 큐의 맨 앞에 있는 값이 꺼낸 값이 currIndex 이상일 때까지 큐에서 값을 꺼낸다.
  3. 큐가 빌 때까지 꺼냈는데도 꺼낸 값이 currIndex 미만이면 남은 값 중 i가 없다는 뜻이므로 다음 i로 넘어간다.
  4. 2에서 꺼낸 값이 currIndex + k보다 크다면, i는 범위 밖에 있는 값이라는 뜻이므로 다음 i로 넘어간다.
  5. 2에서 꺼낸 값이 curr라면
    • $\text{currIndex} \leftarrow \text{curr} + 1$
    • $k \leftarrow k - a$
    • currIndex 이상 currIndex + k 이하의 인덱스에서의 최댓값은 i이므로 i 반환

K = 0인 2번 과정은 단순하므로, 따로 설명하지는 않도록 하겠다. 코드의 30 ~ 31행에 해당한다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

import java.io.*;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class BOJ2812 {
    int n, k;
    int[] numbers;
    Queue<Integer>[] index;

    void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());
        numbers = new int[n];
        index = new Queue[10];
        for (int i = 0; i < 10; i++)
            index[i] = new LinkedList<>();
        String number = br.readLine();
        for (int i = 0; i < n; i++) {
            numbers[i] = number.charAt(i) - '0';
            index[numbers[i]].offer(i);
        }
    }

    int currIndex = 0;

    int greedy() {
        if (k == 0) {
            return numbers[currIndex++];
        }
        int curr;
        for (int i = 9; i >= 0; i--) {
            curr = -1;
            while (!index[i].isEmpty()) {
                curr = index[i].peek();
                if (curr >= currIndex) break;
                index[i].poll();
            }
            if (curr < currIndex || curr > currIndex + k) continue;
            k -= (curr - currIndex);
            currIndex = curr + 1;
            return i;
        }
        return 0;
    }

    void solution() throws IOException {
        input();
        StringBuilder sb = new StringBuilder();
        int length = n - k;
        for (int i = 0; i < length; i++) {
            sb.append(greedy());
        }
        System.out.println(sb);
    }

    public static void main(String[] args) throws IOException {
        new BOJ2812().solution();
    }
}

댓글남기기