백준 2014 자바 - 소수의 곱 (BOJ 2014 JAVA)

문제 : boj2014

 

 

1. 문제 이해

  문제를 다소 이해하기 힘들 수 있는데 문제를 이해하기 쉽게 써보면 다음과 같다. 예를들어 2,5,7이 입력으로 주어졌다면 이하의 수식으로 나온 결과 중 N번째로 작은 수를 구하면 되는 것이다. (단, i,j,k가 모두 0이면 안됨. 그리고 K(k와 다름. 문제에서 주어진 K) 가 늘어나면 물론 i,j,k 외에도 더 추가해주면 됨.)

 

2. 해결 로직 생각해보기

  근데 i, j, k를 임의로 정해서 작은 수를 찾기에는 뭐부터 해야지 작은수부터 차례대로 나올지 알 수 없다. 또한 무한정 i, j, k를 늘려나가기엔 당연히 무리가 있다. 따라서 처음에 주어진 K개를 모두 넣어두고 작은 수부터 차례대로 K개의 소수를 곱해 넣고, 그 결과중에서도 다시 작은 수부터 차례대로 K개의 소수를 곱해넣어주면 된다. 예를들어 2,5,7은 다음과 같이 된다.

 

A. 처음엔 K개를 모두 어딘가에 넣는다. -> [2,5,7]

B. 가장 작은 수인 '2'를 빼내고, K개의 소수인 2,5,7을 뺐던 '2'에 각각 곱해 넣는다. -> [5,7,4,10,14]

C. 다음으로 가장 작은 수인 '4'를 빼내고, K개의 소수를 뺐던 '4'에 각각 곱해넣는다. -> [5,7,10,14,8,20,28]

..

 

이런식으로 N번 수행하면 N번째로 가장 작은 수를 구할 수 있다.

 

 

3. 자료구조 선정

  그럼 로직은 정해졌으니 어떤 자료구조를 써야 적절할지 확인해보자.

A. 중복된 수는 넣으면 안된다. 넣을려면 넣어도 로직상 문제는 없으나, 매우 비효율적으로 동작하게 된다.

B. 현재 들어간 데이터에서 가장 작은 수를 찾을 수 있어야 한다.

 

따라서 가장 적절한 자료구조는 TreeSet이다. 데이터가 정렬되어 들어가 있으므로 바로바로 가장 작은 수를 찾을 수 있고, Set이므로 중복데이터가 들어가지 않는다.

 

 

4. 메모리 초과 해결 및 그 외 주의점

  그런데 이 문제 메모리 제한이 매우 빠듯하다. 특히 자바라 더욱..

ㅠㅠ.. 틀렸습니다가 더 해결하기 쉽지, 메모리 초과가 제일 난감하다.

 

  메모리 초과를 해결하기 위해 넣은 로직은 다음과 같다.

 

A. 문제의 답이 2^31 미만이라 하였으므로, 2^31 이상의 값은 넣지 않는다. 또한 K개가 애초에 오름차순으로 들어왔으므로 넘어선 순간 해당 루프를 중지해도 된다.

 

B. 매번 TreeSet의 최대값을 가지고 있다가 현재 곱셈한 결과가 최대값보다 크고, 남은 N이 TreeSet의 size보다 크다면 애초에 해당 결과는 필요없는 데이터이므로 거기서 해당 루프를 끝내도 된다(백트래킹).

 

  그리고 추가로 2^31 미만 까지의 값이므로 Integer 범위 내에서 해결되긴하지만, 곱셈의 결과 자체도 Integer 범위내에서 해결 가능한 것은 아니다. 따라서 곱셈 결과 자체는 long으로 계산하고 해당 값이 Integer 범위 밖이라면 무시하고, 이내라면 TreeSet에 넣어주면 된다.

 

 

코드 : github

import java.io.DataInputStream;
import java.io.IOException;
import java.util.TreeSet;

public class Main extends FastInput {
    private final static int LIMIT = Integer.MAX_VALUE;

    private void solution() throws Exception {
        int k = nextInt();
        int n = nextInt();

        TreeSet<Integer> ts = new TreeSet<>();
        int[] arr = new int[k];
        for (int i = 0; i < k; i++) {
            arr[i] = nextInt();
            ts.add(arr[i]);
        }

        n--;
        int max = arr[k-1];
        while (n-->0) {
            int cur = ts.pollFirst();
            for (int i = 0; i < k; i++) {
                long tmp = 1l*cur*arr[i];
                if (tmp > LIMIT) break;

                int next = (int)tmp;
                if (ts.size() > n && next > max) break;

                ts.add(next);
                if (max < next) max = next;
            }
        }
        System.out.println(ts.pollFirst());
    }

    public static void main(String[] args) throws Exception {
        initFI();
        new Main().solution();
    }
}

class FastInput {
    private static final int DEFAULT_BUFFER_SIZE = 1 << 16;
    private static DataInputStream inputStream;
    private static byte[] buffer;
    private static int curIdx, maxIdx;

    protected static void initFI() {
        inputStream = new DataInputStream(System.in);
        buffer = new byte[DEFAULT_BUFFER_SIZE];
        curIdx = maxIdx = 0;
    }

    protected static int nextInt() throws IOException {
        int ret = 0;
        byte c = read();
        while (c <= ' ') c = read();
        do {
            ret = ret * 10 + c - '0';
        } while ((c = read()) >= '0' && c <= '9');
        return ret;
    }

    private static byte read() throws IOException {
        if (curIdx == maxIdx) {
            maxIdx = inputStream.read(buffer, curIdx = 0, DEFAULT_BUFFER_SIZE);
            if (maxIdx == -1) buffer[0] = -1;
        }
        return buffer[curIdx++];
    }
}