Chap 16. DP - Q35. 못생긴 수

  • 0
  • 0
0
0

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

결론

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

C. 🧐 문제 해설

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

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

a. 책 답안

python-for-coding-test/5.py at master · ndb796/python-for-coding-test (github.com)

참고문헌

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

0분전
작성된 댓글이 없습니다. 첫 댓글을 달아보세요!
    댓글을 작성하려면 로그인이 필요합니다.