[이코테] 다이나믹 프로그래밍 문제 - 못생긴 수 python

난이도 : ●◐○ | 풀이 시간 : 30분 | 시간 제한 : 1초 | 메모리 제한 : 128MB | 기출 : Google 인터뷰

문제

• 2, 3, 5만을 소인수로 가지는 수를 못생긴 수라고 한다.
• n번째 못생긴 수를 찾는 프로그램을 작성하라.

입력조건

• 첫째 줄에 n이 입력된다.(1<=n<=2,000)

출력조건

• n번째 못생긴 수를 출력한다.

 

입력예시

10

출력예시

4

 

아이디어

• 못생긴 수를 저장할 집합 s를 생성한다.
• 집합 s에 첫 번째 못생긴 수인 1을 추가한다.
• x를 첫 번째 못생긴 수인 1로 초기화한다.
• while문을 돌면서 x*2, x*3, x*5한 것이 s에 없다면 추가한다.
• 집합 s의 원소 개수가 n이 되면 반복을 종료한다.
• s에 마지막으로 추가된 수를 출력한다.

오답코드

n = int(input())
s = set()
s.add(1)
x = 1
flag = False
while True:
    for i in (x*2,x*3,x*5):
        if i not in s:
            s.add(i)
        if len(s)==n:
            flag = True
            break
    if flag:
        break
    x += 1

print(list(s)[-1])

• 집합의 길이가 n이 되었을 때 집합에 n번째로 추가된 수가 항상 n번째 못생긴 수라는 보장이 없기 때문에 틀렸다.
• x*2, x*3, x*5 중에 가장 작은 값으로 다시 *2, *3, *5를 해야 바르게 n번째 못생긴 수를 구할 수 있다는 것을 깨달았다.

 

정답코드

n = int(input())

# n개의 못생긴 수를 저장할 리스트
ugly = [0]*n
# 첫 번째 못생긴 수는 1
ugly[0] = 1

# 2배, 3배, 5배를 위한 인덱스
i2=i3=i5=0
# 첫 번째 못생긴 수 1의 2배, 3배, 5배한 값으로 초기화
next2,next3,next5=2,3,5

for i in range(1,n):
    # 2, 3, 5를 곱한 것 중 가장 작은 수를 선택함
    ugly[i] = min(next2,next3,next5)

    if ugly[i]==next2:
        i2+=1
        next2 = ugly[i2]*2
    if ugly[i]==next3:
        i3+=1
        next3=ugly[i3]*3
    if ugly[i]==next5:
        i5+=1
        next5=ugly[i5]*5
print(ugly[n-1])

후기

• i2, i3, i5를 활용하는 방법이 인상적이었다.

 

출처

이것이 취업을 위한 코딩테스트다 with 파이썬