[Google 인터뷰] 못생긴 수

문제

---

못생긴 수란, 소인수분해 했을 경우 나오는 소인수가 2, 3 그리고 5뿐인 수를 이야기 하며, 이를 수열로 늘어놓으면 다음과 같다.

 

1, 2, 3, 4, 5, 6, 8, 9, 10, 12...

 

이는 처음나오는 10개의 못생긴 수이며, 편의상 1을 포함하도록 하자. 정수 n이 주어졌을 때, n번째 못생긴 수를 출력하는 프로그램을 작성하라.

 

 

 

입출력

---

입력	출력
10	12
4	4

 

 

 

초기접근

---

1001크기의 리스트를 만들고 각 인덱스에 1이 표시되어있으면 못생긴 수로 판단한다.

dp = [0]*1001

 

dp[1], dp[2], dp[3], dp[5]를 1로 표시한다.

0인 값들을 2,3,5로 나눠보고 나누어떨어지면 1로 표시한다.

1로 표시된 것들의 개수를 세어나가면서 n이 되면 종료하고 해당 인덱스를 출력한다.

 

 

 

해결 아이디어

---

초기접근대로 코드를 작성하려 했지만 중복되는 계산이 너무많고 공간도 불필요하게 차지하는 것 같아서 다른 방법을 생각했다.

 

1. 중복되는 계산을 방지해야한다.

2. 불필요한 공간차지를 없앤다.

 

"못생긴 수만 세어보자"

• 1부터 시작해서 2, 3, 5를 곱한 수들이 못생긴 수이고 못생긴 수들에 2, 3, 5를 곱한 것도 못생긴 수이다.
• 못생긴 수 중에서 작은수부터 2,3,5를 곱해나가며 못생긴 수를 센다.
• 중복되는 계산은 건너뛴다.

 

해결방법

1. 못생긴 수들을 담을 리스트가 필요하고
2. 작은수부터 빼내야 하니까 최소 힙을 사용한다.
3. 중복되는 계산을 건너뛰기 위해 이미 있는 데이터는 건너뛴다
4. n번째 못생긴 수를 찾기 위한 answer 리스트를 만든다

 

 

정답코드

---

import heapq

n = int(input())

answer = []
data = []
data.append(1)

while len(answer) < n:
    target = heapq.heappop(data)
    a = [0]*3
    a[0], a[1], a[2] = target*2, target*3, target*5

    for i in a:
        if i not in data:
            heapq.heappush(data, i)

    answer.append(target)

print(answer[-1])