백준 2014 소수의 곱 풀이 (feat. JAVA & C#)

골드 상위권 문제는 늘 이런 식이다...

쉬운듯 하면서 함정을 파놓지

이 문제는 PQ문제다

근데 곱셈의 중복처리를 해줘야하니까? HashSet도 필요하고...

2 x 3과 3 x 2는 같으니까? 미리 가지치기(예외처리)도 필요한...

그런 몹쓸 문제 되시겠다

 

아래는 내가 제일 헷갈렸던 포인트를 줄줄줄 설명하듯 적어놨음

---

이게 뭐냐고! 대체 뭐냐고!! 

// 중복 제거: 오름차순 생성만 허용
if (curr % nums[j] == 0) break;

뭘까 진짜... 수십번을 생각했더랬다

근데 도저히 모르겠음

이 날은 도저히 모르겠음을 인정하고 하루 방치해뒀다

실제로 더 이상 머리가 굴러가지 않는 문제는?
하루를 냅두고 숙성시켰다가 다음날 꺼내보면 무의식이 이해를 해두는 경우도 종종 있다
- 의사쌤 유튭채널 오피셜 말씀이었음

 

아무튼 저것의 요지는? 기존의 소수로 나눴을 때 깔끔히 나눠 떨어지는 친구라면???
시도해볼 필요가 없단 뜻이다

 

예를들면 아래와 같은 조건을 말한다

curr = 6

nums[j] = 2

 

이 경우 6은 2로 깔끔하게 나눠떨어진다

 

즉, 6에 소수를 곱해 생산할 수 있는 숫자들은?

이미 2에 소수들을 곱해 만들어낸 숫자들!!로써

1) 이미 PQ에 넣어두었거나

2) 앞으로 넣어둘 숫자란 의미가 된다

 

정리하면 이미 있거나, 앞으로 나올 예정인 숫자들을 또 계산하는 것은 메모리 낭비, 시간 낭비라는 의미이고 그렇기 때문에 중단하는 것이다

---

---

문제 분석 및 사고의 흐름 정리

/*
[백준]
2014, 소수의 곱

[문제파악]
K개의 소수가 있다.
이때, 이 소수들 중에서 몇 개를 곱해서 얻게 되는 수들이 있을 것이다.
소수들을 선택할 때에는 같은 수를 선택해도 되며, 주어지는 소수 자체도 포함시키자.
예를 들어 세 소수가 2, 5, 7이었다면, 이러한 곱들을 오름차순으로 나타내 보면, 2, 4, 5, 7, 8, 10, 14, 16, 20, 25, 28, 32, 35, 등이 된다.
K개의 소수가 주어졌을 때, 이러한 소수의 곱들 중에서 N번째 수를 구해 보자.
단 정답은 2^31보다 작은 자연수이다.

[입력]
첫째 줄에 K(1 ≤ K ≤ 100), N(1 ≤ N ≤ 100,000)이 주어진다.
다음 줄에는 K개의 소수가 오름차순으로 주어진다.
같은 소수가 여러 번 주어지는 경우는 없으며, 주어지는 소수는 모두 541보다 작거나 같은 자연수이다.

[출력]
첫째 줄에 문제에서 설명한 대로 소수의 곱을 나열했을 때, N번째 오는 것을 출력한다.

[구현방법]
- C# 기본적인 것은 됐고, 이제 자료구조를 빡세게 써볼 시간..!
- N번쨰 숫자까지니까 K의 제곱수로 N을 초과하는데까지만 구하고 첫번째 숫자부터 제곱해서 Queue에 밀어넣는다
- 그러고 나면 나중에 Q 안에는 정렬도 되어있고, N을 초과하는 갯수도 구할 수 있음
- 근데 이 방식은 그리면서 해봤는데 터무니 없다 첫번째, 두번째까지면 어떻게 구하겠지만 3제곱만 해도, 5가 곱해야할 분량은 9개... K는 최대 100개까지 들어올 수 있는데, 값을 미리 구하고 있는다는 것은 말이 안될 것 같다

- 이건 푸는 방법이 있다
    1) 우선 소수 K를 입력받는다
    2) 우선순위 큐 pq에 다 밀어넣고, visited라는 HashSet에 넣은 값들을 기록한다 (중복 제거를 위함)
    3) 매 반복마다 가장 작은 수 x를 pq에서 꺼낸다 (제일 앞에 있는 숫자가 될테죠?)
    4) x에 모든 소수를 곱하고, 소수를 곱한 새로운 수(x * p)를 pq에 넣는다 (방문하지 않았던 값들만)
    5) 위 과정을 N번 반복하면, pq에 들어있을 가장 작은 수가 N번째로 작은 수가 됨

- 이렇게 구하면 시간복잡도를 따져도 N번만큼만 루프를 돌게된다
- 내가 초기에 짠 것처럼 N * N -1 => N^2이 되지 않음

[보완점]
1) 런타임 에러 (Segfault)뜸
    - 이거 StreamReader 쓸거면 그거만 쓰고, Console.ReadLine() 쓸거면 그거만 써야함.

2) 메모리 초과
    - 모든 걸 PQ에 밀어넣으니까 메모리 터짐...
    - 슬라이딩 윈도우 기법 쓰란다.. 그게 뭔데...
    - 그래도 터지는데...?
    - 설마 C#이라서...? JAVA로 풀면 되려나?
    - 자바로 해도 여전히 메모리 초과
    - 어려운데.. 전략이 잘못됐단 소린데.. Set이랑 PQ에 너무 많이 집어넣는게 문제인듯 함
*/

---

JAVA 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        HashSet<Long> isVisited = new HashSet<>();
        PriorityQueue<Long> pq = new PriorityQueue<>();

        int K = Integer.parseInt(st.nextToken());  // 정수 갯수
        int N = Integer.parseInt(st.nextToken());  // N번째 숫자

        int[] nums = new int[K];

        // 소수 입력 받기
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < K; i++) {
            nums[i] = Integer.parseInt(st.nextToken());
            isVisited.add((long) nums[i]);  // 방문처리
            pq.add((long) nums[i]);  // pq에 삽입
        }

        long curr = 0;

        // N번째 숫자 찾기
        for (int i = 1; i < N; i++) {
            curr = pq.poll();

            for (int j = 0; j < K; j++) {
                long next = curr * nums[j];

                // 2^31을 넘지 않는다는 것이 문제 조건이니 혹시라도 초과했다면 더 볼 것없이 break;
                if ((1L << 31) <= next) break;

                pq.add(next);

                // curr이 nums[j]로 나누어떨어진다는 것은?
                // 해당 수(next = curr * nums[j])가 이미 더 작은 소수들로 구성된 곱에서 생성됐거나, 앞으로 생성될 수 있음을 의미한다
                // 즉, 중복 생성을 막기 위해 이후 루프는 중단해야 한다
                // 다만, 이것을 PQ에 next를 넣기 전에 진행하지 않는 이유는, 소수와 처음 곱한 next는 PQ에 들어갈 가능성이 높기 때문이다
                // 두번째 줄에서 말한 '이미 생성해서 넣은 수 or 앞으로 생성해서 넣어둘 수'에 해당할 수 있기 때문임
                if (curr % nums[j] == 0) break;
            }
        }

        System.out.println(pq.peek());
    }
}

---

C# 풀이

using System;

class Program
{
    public static void Main()
    {
        string[] input = Console.ReadLine().Split();
        int K = int.Parse(input[0]);
        int N = int.Parse(input[1]);

        int[] nums = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
        HashSet<long> isVisited = new HashSet<long>();
        PriorityQueue<long, long> pq = new PriorityQueue<long, long>();

        // 초기에 입력 받은 소수들을 방문처리하고 pq에 추가
        for (int i = 0; i < K; i++) {
            long temp = nums[i];

            isVisited.Add(temp);
            pq.Enqueue(temp, temp);
        }

        long curr = 0; 

        for (int i = 1; i < N; i++) {
            curr = pq.Dequeue();

            for (int j = 0; j < K; j++) {
                long next = curr * nums[j];

                if ((1L << 31) <= next) break;  // 2^31 이상이면 더 볼 것 없다
                pq.Enqueue(next, next);
                if (curr % nums[j] == 0) break;  // 현재 값이 초기에 입력 받은 소수들로 나눠진다면 이후 값들은 더 볼 것 없이 중단
            }
        }

        Console.WriteLine(pq.Peek());
    }
}

---

번외 - C# 풀이... 4명...?

와 이거 ㅋㅋㅋㅋ C#으로 푼 사람 나 포함 네명 밖에 없네...

하긴 누가 코테를 C#으로 하겠어..

C++을 두고...

나는 왜...