[BOJ] 2014 소수의 곱 - Java

[원본링크] 

https://adorable-aspen-d23.notion.site/BOJ-2014-f2f38c50eb9b490284b602995b8a7472

[BOJ] 2014

 

[풀이]

• 주어진 소수를 이용하여 곱으로 만들 수 있는 수들 중 N번째 수를 구하는 문제이다.
• 배열을 계속해서 정렬 시켜주면 시간초과가 날 것이므로 priority queue를 사용하는 문제임을 떠올렸다.
• 처음에 중복 제거를 위해 pq.contains 함수를 사용했는데, 시간초과가 났다. O(N)의 시간복잡도를 가지기 때문인 것 같다.
• → 중복 제거를 위해 modulo 연산을 사용했다.

[코드]

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

public class Boj2014_소수의곱 {
    static int K,N;
    static long[] num;
    static PriorityQueue<Long> pq = new PriorityQueue<>();

    public static void main(String[] args) throws Exception{
        System.setIn(new FileInputStream("src/main/java/input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        K = Integer.parseInt(st.nextToken()); //1~100개 소수
        N = Integer.parseInt(st.nextToken()); //1~10000번째 수 구하기
        num = new long[K];

        st = new StringTokenizer(br.readLine());
        for(int i=0;i<K;i++){
            num[i] = Long.parseLong(st.nextToken());
            pq.add(num[i]);
        }

        int count = 1;
        long now = 0;
        while(count < N+1){ //중단조건 : count == N+1일 때 종료
            count++;
            now = pq.poll();
            for(long it:num){
                //if(!pq.contains(now * it)) //contains는 O(N)의 시간 복잡도를 갖는다.
                pq.add(now * it);

                if(now % it == 0){ //중복된 수 제거하기
                    // (now>=it 인 상황에서 now가 it의 배수이면 거기까지만 연산을 진행한다.)
                    //System.out.println("now = "+now+" it = "+it + " multi = "+ now*it);
                    break;
                }

            }
        }
        System.out.println(now);
    }
}

얻어가는 것

• Priority Queue
  • But, iterate하는 중에 맨 앞에 삽입을 하게 되면 error발생
  • → iterate 할거면 맨 뒤에 삽입되도록 해야한다.
• : 원소 삽입 시 특정 조건으로 정렬을 해준다.
• 시간초과
  • 생각보다 깐깐하다. 중복 제거를 신경쓰자.
• Modulo 연산(나머지 연산)

4%2 = 0
4%3 = 1

2%4 = 2
3%4 = 4

느낀점

"220203"

소요 시간 : 2h

• 사실 아직도 중복 제거할 때 왜 modulo연산을 통해서 제거하는지 잘 모르겠다
• 써봤는데도 모르겠는데 나중에 다시 한 번 보는걸로...