백준 2014번 소수의 곱 :: 마이구미

이번 글은 백준 알고리즘 문제 2014번 "소수의 곱" 을 다뤄본다.

문제 풀이는 큐 중에서도 우선순이 큐를 활용하여 해결할 수 있다.

정답 비율과 제출 수를 보면 어려운 문제에 속한다.

K개의 소수가 있다. 이 때, 이 소수들 중에서 몇 개를 곱해서 얻게 되는 수들이 있을 것이다. 소수들을 선택할 때에는 같은 수를 선택해도 되며, 주어지는 소수 자체도 포함시키자.

예를 들어 세 소수가 2, 5, 7이었다면, 이러한 곱들을 오름차순으로 나타내 보면, 2, 4, 5, 7, 8, 10, 14, 16, 20, 25, 28, 32, 35, 등이 된다.

K개의 소수가 주어졌을 때, 이러한 소수의 곱들 중에서 N번째 수를 구해 보자. 단 정답은 32-bit integer 이내이다.

본인은 처음에 K개가 100개밖에 안되기 때문에 브루트 포스로 접근해도 사실상 해결하리라 생각했다.

소수의 곱은 아래와 같이 뽑을 수 있다.

2 3 5 7

2를 기준으로 모든 수와 곱, 3을 기준으로 모든 수와 곱, 5를 기준으로 모든 수와 곱, 7을 기준으로 모든 수와 곱.

즉, 입력 소수들을 배열에 저장해놓고, 배열의 값들과 한번씩 곱한다.

for (int i = 0; i < k; i++) {
    prime[i] = sc.nextInt();
}

for (int i = 0; i < k; i++) {
    int value = n * prime[i]
    ......
}

이러한 흐름을 큐를 활용하면서 아래와 같은 흐름을 가져가면 된다.

1. 소수의 곱을 구해서 큐에 넣는다.
2. 큐 안에서 최소 값을 구한다.
3. 최소 값을 뺀다.

1번은 단순히 곱을 하면 된다.

2번은 우선순위를 낮은 값에 주어 오름차순으로 정렬하는 우선순위 큐를 이용한다.

3번은 큐는 현재 오름차순으로 되어있기 때문에 큐의 head값이 최소값이다.

2 3 5 7

2 * 2, 2 * 3, 2 * 5, 2 * 7 = > Priority Queue(2,3,4,5,6,7,10,14)
3 * 2, 3 * 3, 3 * 5, 3 * 7 = > Priority Queue(3,4,5,6,6,7,9,10,14,15,21)
4 * 2, 4 * 3, 4 * 5, 4 * 7 = > Priority Queue(4,5,6,6,7,8,9,10,12,14,15,20,21,21) 
..........

이와 같은 경우, 한번의 루프에 한번의 head값이 빠져나오게 된다.

이 말은, n번 루프를 돌면, n번째 수가 나오게 된다.

우선순위 큐를 통해 매번 오름차순으로 정렬되기 때문에 head값이 최소 값이기 때문에 가능하게 된다.

for (int i = 0; i < n; i++) {
    head = q.poll();

    for (int j = 0; j < k; j++) {
        long value = head * prime[j];
        q.add(value);
    }
}

하지만, 이 방법에는 조건이 필요하다.

소수의 모든 경우를 큐에 다 넣기 때문에, 중복되는 수가 발생한다. ex) 2 * 3, 3 * 2

그렇기에 큐에서 중복되는 수를 제거하는 작업이 필요하다.

중복되는 수를 제거하는 작업에서 많은 시간이 소요되게 된다.

실제로 이러한 방법으로 제출시 시간이 5800ms가 나온다.

다른 풀이 방법으로는 100~200ms가 된다.

해결법은 처음부터 중복되는 수를 큐에 넣지 않으면, 불필요한 시간이 낭비되지 않는다.

(실제로 중복 제거 작업이 없다면, 200ms로 문제를 해결할 수 있다.)

결국 중복은 아래와 같이 표현할 수 있다.

우리는 빨간 부분만을 구하면 된다.

하지만, 중복 때문에 모든 점들을 구하고 있는 상황이다.

빨간 부분만 구해주면 되기 때문에, 하나의 조건을 추가해주면 해결된다.

for (int i = 0; i < n; i++) {
    head = q.poll();

    for (int j = 0; j < k; j++) {
        long value = head * prime[j];
        q.add(value);

        if (head % prime[j] == 0) {
            break;
        }
    }
}

Github - https://github.com/hotehrud/acmicpc/blob/master/algorithm/Queue/2014.java

private void solve() {
    int k = sc.nextInt();
    int n = sc.nextInt();
 
    // http://mygumi.tistory.com/183
    // 소수 리스트, 소수와 비교하여 곱한 값 넣는 큐, 최종 리스트
    // 큐의 맨 앞 요소를 빼서 각 소수를 곱하면서 큐에 다시 넣을 것이다.
 
    long[] prime = new long[k];
    PriorityQueue<Long> q = new PriorityQueue<>();
 
    for (int i = 0; i < k; i++) {
        prime[i] = sc.nextInt();
        q.add(prime[i]);
    }
 
    long head = 0;
 
    for (int i = 0; i < n; i++) {
        // n번째 뺀 값이 n번째 수가 된다.
        head = q.poll();
 
        // 큐를 활용하여 삽입마다 오름차순으로 정렬됨으로써 원하는 값들을 리스트에 저장 가능.
        for (int j = 0; j < k; j++) {
            long value = head * prime[j];
            q.add(value);
 
            if (head % prime[j] == 0) {
                break;
            }
        }
    }
    System.out.println(head);
}