Q35. 못생긴 수

못생긴 수 = 2,3,5만을 소인수로 가지는 수

1은 못생긴 수라고 가정

n이 주어질 때 n번째 못생긴 수를 출력

1 <= n <= 1000

 

음 일단.. 내 첫 발상은 길이가 충분히 긴 리스트를 만들어서 2의배수 3의배수 5의배수를 채워넣고 앞에서부터 몇 번째인지 체크하는 방법이다. n이 최대 1000이면 넉넉잡아 2000정도 길이의 리스트를 만들면 1000번째 수까지 찾을 수 있을거고 시간복잡도는 리스트의 길이가 N일때 O(N). 정확히는 2,3,5 배수 체크하는데 각각 N씩 쓰고 몇 번째인지 체크하는데에 N 써서 4N일거같다. 근데 이렇게 간단한 문제가 Google 인터뷰에 나온다고? 뭔가 더 좋은 방법이 있을거같은데.. 흠...ㅠ 아무래도 꺼림칙하다.

 

정답 확인 후

보니까 2 3 5의 배수를 이용해서 찾아가는건 비슷한데 문제는 메모리 효율적으로 구현하는 부분인거같다. 위 방법은 너무 메모리 비효율적이다.

 

이거 찾아보니까 웰노운같은데 풀이방법이 다양하다 ㄷㄷ..

 

n = int(input())

ugly = [0] * n

ugly[0] = 1

 

i2 = i3 = i5 = 0

n2, n3, n5 = 2, 3, 5

 

for l in range(1, n):

    ugly[l] = min(n2,n3,n5)

    if ugly[l] == n2:

         i2 += 1

         n2 = ugly[i2] * 2

    if ugly[l] == n3:

         i3 += 1

         n3 = ugly[i3] * 3

    if ugly[l] == n5:

         i5 += 1

         n5 = ugly[i5] * 5

 

print(ugly[n-1])

 

원리를 이해하는데 시간이 조금 걸렸다. 매우 흥미로운 알고리즘인거같다.

근데 이걸 정답을 안봤으면 어떻게 발상했어야 됐을까?;;