Chap 16. DP - Q35. 못생긴 수

@mildsalmon·2021-10-30 10:14

1. 못생긴 수

난이도
- 중하
풀이 시간
- 30분
시간 제한
- 1초
메모리 제한
- 128 MB
출처
- google 인터뷰

A. 📜 문제

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

a. 예를 들면.

11번째 못생긴 수는 15입니다.

b. 입력 조건

첫째 줄에 n이 입력됩니다.
- 1 <= n <= 1,000

c. 출력 조건

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

d. 테스트 케이스

입력 예시
```
10
```
```
4
```
출력 예시
```
12
```
```
4
```

B. 💡 내 답안

a. 😊 1차 시도 (성공)


n = int(input())

array = list()
array.append(1)

num = [2, 3, 5]

for i in range(1000):
    temp = [array[i] * j for j in num]

    array += temp
    array = set(array)
    array = list(array)
    array.sort()

print(array[n-1])

b. 😊 2차 시도 (효율성을 더 높임)


n = int(input())

array = list()
array.append(1)

num = [2, 3, 5]

for i in range(n):
    temp = [array[i] * j for j in num]

    array += temp
    array = set(array)
    array = list(array)
    array.sort()

print(array[n-1])

a. 🙄 회고

내 풀이

처음에는 효율성을 생각해서, 못생긴 수가 아닌 수를 구하는 방식을 생각해봤다.
- 1 ~ 1,000까지의 수에서 소수(2, 3, 5를 제외한)를 제외하면 구할 수 있다.
- 다만, 소수 판별을 위한 코드를 작성해야해서 시간복잡도가 증가할 것이라 생각했다.
두번째는, 리스트에 1을 넣고 2, 3, 5를 곱해주고 리스트에 다시 넣는 것을 반복한다. 이 과정에서 중복되는 수를 제거하기 위해 set 자료형을 사용하고, 다시 list 자료형으로 형변환을 하면서 정렬을 수행했다.
- 삽입정렬을 수행했으면, 더 빠르게 해결할 수 있었을지도 모르겠다.