[BOJ] 2014. 소수의 곱(Greedy, 탐욕 + 우선순위 큐(힙)).py

#. Problem

https://www.acmicpc.net/problem/2014

* The copyright in this matter is in BOJ

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

Greedy 문제에서 가장(?)어려운 문제라고 한다.

이 문제와 유사한 형태의 문제들이 코딩 테스트에 종종 나오고 

정답률도 낮다고 한다...

잘 준비해놓자!

먼저 이 문제는 Heap(Priority queue)을 사용해야 한다.

heap은 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나오게 된다.

우선순위는 우리가 정해줄 수 있는데, 최댓값이 될 수도, 최솟값이 될 수도 있다. 

여기서는 최솟값, 즉 작은 숫자가 우선순위를 갖게 된다.

입력이 아래와 같다면

[2, 3, 5, 7]

먼저 가장 작은 값인 2가 나오게(pop)될 것이다.

그 다음 이 숫자 2와 입력된 소수를 곱하여 만들 수 있는 숫자를 heap에 넣어준다.

그러면

[3, 4, 5, 7, 6, 10, 14] 가 될 것이다.

기존 3, 5, 7 에서 2*2, 2*3, 2*5, 2*7 이 push 되었는데 작은 숫자가 우선순위를 가지므로

[3, 4, 5, 7, 6, 10, 14] 가 된 것이다.

또 heap에서 빼보자(pop)

차란~ 3이 나왔다.

그럼 또 3과 입력된 소수를 곱하여 만들 수 있는 숫자들 heap에 넣어보자.

[4, 6, 5, 7, 14, 10, 6, 9, 15, 21]

이런 식으로 쭈루루룩 동작시키다보면 

[5, 6, 6, 7, 8, 10, 21, 9, 15, 14, 12, 20, 28]

[6, 6, 10, 7, 8, 10, 15, 9, 15, 14, 12, 28, 20, 21, 25, 35]

...

[27, 30, 28, 30, 35, 28, 30, 32, 36, 40, 40, 75, 45, 63, 36, 35, 45, 70, 48, 49, 42, 42, 50, 125, 168, 56, 98, 120, 90, 147, 140, 42, 112, 60, 105, 105, 80, 84, 54, 100, 60, 50, 63, 48, 72, 70, 75, 126, 175]

[28, 30, 28, 30, 35, 45, 30, 32, 36, 40, 40, 54, 56, 63, 36, 35, 45, 70, 48, 49, 42, 42, 50, 75, 81, 175, 98, 120, 90, 147, 140, 42, 112, 60, 105, 105, 80, 84, 54, 100, 60, 50, 63, 48, 72, 70, 75, 126, 125, 168, 135, 189]

이렇게 된다. 

위 과정이 반복되면서 N번째 수를 체크해주고,

N번째 도달 시 동작을 멈추고 해당 수를 출력해주면 되겠다. 

Ah! 그리고 여기서 중간에 체크해줘야할 부분은 

위 과정이 반복되면서 2 * 2 * 3 = 12, 와 2 * 3 * 2 = 12 와 같이 순서만 다를 뿐 중복되는 숫자가 발생할 수 있는데

이를 방지하기 위하여 중복 체크를 해주고 중복일 경우 pass해주면 된다.

#. Code

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

import heapq import copy   K, N = map(int, input().split()) p_lst = list(map(int, input().split()))   lst, ck = copy.deepcopy(p_lst), set()   heapq.heapify(lst) ith = 0   while ith < N:     mn = heapq.heappop(lst)     if mn in ck:         continue     ith += 1     ck.add(mn)     for i in p_lst:         if mn * i < 2 ** 32:             heapq.heappush(lst, mn*i)   print(mn)

cs

line 7) 몇 번째 소수들의 곱을 찾을지 찾기 위해 입력 받은 리스트를 deepcopy 해주고,

    2*2*3, 2*3*2 와 같이 곱의 순서는 다르지만 결과는 같은 중복된 수를 체크하기 위해 set() 자료형 변수 준비  

line 9) Heap 생성, 기존 lst 리스트를 힙으로 변환

line 12~20) 소수의 곱들 중 N번째 수를 찾을 때 까지 반복

line 13) heap의 가장 꼭대기 값은 최솟값을 가지고 있다. pop을 해주면 lst의 최솟값을 반환

line 14) heap에서 pop해준 최솟값이 중복된 값이라면 continue

line 16) heap에서 pop해준 최솟값이 새로운 값이라면 ith++

line 17) 새로운 값을 다시 set() 자료형에 넣어준다. 

line 18) 그리디의 핵심, heap에 어떤 방식으로 숫자를 넣을 것인가가 중요

해당 최솟값에 가지고 있는 소수들을 곱한 값을 모두 heap에 push