[Google 인터뷰] 못생긴 수

못생긴 수란 오직 2, 3, 5만을 소인수로 가지는 수를 의미합니다. 다시 말해 오직 2, 3, 5를 약수로 가지는 합성수를 의미합니다. 1은 못생긴 수라고 가정합니다. 따라서 못생긴 수들은 {1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, ...} 순으로 이어지게 됩니다. 이때 n번째 못생긴 수를 찾는 프로그램을 작성하세요. 예를 들어 11번째 못생긴 수는 15입니다.

 

입력 조건

- 첫째 줄에 n이 입력됩니다. (1 <= n <= 1000)

 

출력 조건

- n번째 못생긴 수를 출력합니다.

 

입력 예시1

10

 

출력 예시1

12

 

입력 예시2

4

 

출력 예시2

4

 

---

 간단하게 풀 수 있을 줄 알았으나 생각보다 까다로운 문제였습니다. 처음에 생각한 방법론은 1부터 차례로 수를 증가시키면서 2를 곱한 값, 3을 곱한 값, 5를 곱한 값을 테이블에 입력합니다. 이후 입력되지 않은 값을 제외하고 나머지에 대해 n번째 인덱스의 값을 구하면 정답을 '구할 수는 있습니다'. 아래는 소스코드입니다.

 

n = int(input())

table = [0] * int(1e6)
table[1] = 1

for i in range(1, n):
    table[i * 2] = table[i] * 2
    table[i * 3] = table[i] * 3
    table[i * 5] = table[i] * 5
    
table = [x for x in table if x > 0]
print(table[n - 1])

 

 이렇게 구현하는 방식의 장점은 간단하다는 것입니다. 다만 치명적인 문제가 존재하는데, 바로 Memory leakage입니다. 예를 들어 [1, 2, 3, 4, 5 6, 0, 8, 9, 10, 0, 12, 0, 0, 15, ...]와 같이 못생기지 않은 수에 대해서 0으로 처리하기 때문에, n번째 데이터를 구해야함에도 불구하고 n보다 긴 배열을 요구할 뿐더러, 얼마나 길어질지도 알 수가 없습니다.

---

 따라서 조금 복잡하더라도 다음과 같이 코드를 작성하는 것이 바람직합니다.

n = int(input())

table = [0] * n
table[0] = 1

i2 = i3 = i5 = 0
next2, next3, next5 = 2, 3, 5

for l in range(1, n):
    table[l] = min(next2, next3, next5)
    if table[l] == next2:
        i2 += 1
        next2 = table[i2] * 2
    if table[l] == next3:
        i3 += 1
        next3 = table[i3] * 3
    if table[l] == next5:
        i5 += 1
        next5 = table[i5] * 5

print(table[n - 1])

 

 위 코드의 장점은 결국 DP table의 길이가 n임을 보장한다는 것입니다. 모든 수에 대해서 2를 곱한 값, 3을 곱한 값, 5를 곱한 값을 고려해야하기 때문에 각 수가 곱해진 위치를 저장하는 변수인 i2, i3, i5를 선언합니다. 또한 최소값을 비교하기 위한 변수인 next2, next3, next5도 선언해줍니다.

i2 = i3 = i5 = 0
next2, next3, next5 = 2, 3, 5

 

 이후 테이블을 순회하면서 next2, next3, next5 중 가장 작은 값을 골라 해당 인덱스에 업데이트합니다. i2, i3, i5는 각각 1씩 증가하며 모든 수에 대해 곱해짐을 보장하고, 다음 수는 next2, next3, next5 또한 각각 2, 3, 5를 곱한 수로 업데이트해줍니다.

 

for l in range(1, n):
    table[l] = min(next2, next3, next5)
    if table[l] == next2:
        i2 += 1
        next2 = table[i2] * 2
    if table[l] == next3:
        i3 += 1
        next3 = table[i3] * 3
    if table[l] == next5:
        i5 += 1
        next5 = table[i5] * 5

 

 결과적으로 n=10일 때 얻을 수 있는 테이블의 형태는 다음과 같습니다.

[1, 2, 3, 4, 5, 6, 8, 9, 10, 12]