# Chap 16. DP - Q35. 못생긴 수

- Author: @mildsalmon
- Published: 2021-10-30
- Updated: 2021-10-30
- Source: http://blex.me/@mildsalmon/chap-16-dp-q35-%EB%AA%BB%EC%83%9D%EA%B8%B4-%EC%88%98
- Tags: 파이썬, 한빛미디어, 나동빈, 코딩테스트, 문제, 풀이, dp

---

# 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차 시도 (성공)

```python

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차 시도 (효율성을 더 높임)

```python

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 자료형으로 형변환을 하면서 정렬을 수행했다.
	- 삽입정렬을 수행했으면, 더 빠르게 해결할 수 있었을지도 모르겠다.

> 결론

- 파이썬의 특징을 잘 살려서 푼 문제같다.
- 다만, 1차 시도에 for문을 n번 반복하는 것이 아닌, 1000번 반복한 점은 조금만 더 생각을 하고 풀었어야 하지 않나 싶다.

### C. 🧐 문제 해설

> 이해한 내용을 바탕으로 작성했습니다.

![](https://static.blex.me/images/content/2021/10/30//2021_10_30_10_pViv02UHYKB7UNCUJ6Ve.jpg)

이걸 DP로 생각해본다면, 못생긴 수로 결정된 것, 즉 i번째 수는 dp 테이블에 저장하는 방식으로 표현할 수 있겠다.

##### a. 책 답안

[python-for-coding-test/5.py at master · ndb796/python-for-coding-test (github.com)](https://github.com/ndb796/python-for-coding-test/blob/master/16/5.py)

# 참고문헌

나동빈, "이것이 취업을 위한 코딩 테스트다 with 파이썬", 초판, 2쇄, 한빛미디어, 2020년