[Google 인터뷰] 못생긴 수

[Google 인터뷰] 못생긴 수

다이나믹

 

해당문제는 설명이 잘되어 있는  https://leeyeongeol.github.io/%EC%9D%B4%EC%BD%94%ED%85%8C/%EC%9D%B4%EC%BD%94%ED%85%8C-%EB%AA%BB%EC%83%9D%EA%B8%B4-%EC%88%98/ 를 참고하여 작성하였음

 

 

 

[문제]

 

 

 

[과정]

 

이 문제는 가능한 못생긴 수를 앞에서부터 하나씩 찾는 방법으로 해결할 수 있다. 못생긴 수들은 [1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, …]와 같이 끊임없이 존재한다. 이때 못생긴 수에 2, 3 혹은 5를 곱한 수 또한 ‘못생긴 수’에 해당한다는 점이 포인트이다.

 

2의 배수 변수, 3의 배수 변수, 5의 배수 변수에 대하여 각각 ‘가장 작은 못생긴 수’부터 오름차순으로 하나씩 확인하면서, 각 배수를 곱한 값도 ‘못생긴 수’가 될 수 있도록 처리하면 정답 판정을 받을 수 있다.

 

예를 들어 먼저 못생긴 수로 1이 있다고 해보자. 이때 각각 2의 배수, 3의 배수, 5의 배수를 구하면 다음과 같다.

• 2의 배수: 1 x 2 = 2
• 3의 배수: 1 x 3 = 3
• 4의 배수: 1 x 4 = 4

이로써 우리는 새롭게 2, 3, 4 또한 못생긴 수에 해당한다는 것을 알 수 있다. 따라서 이를 고려했을 때, 전체 못생긴 수는 {1, 2, 3, 4}가 된다.

 

첫 번째로 못생긴 수인 1에 이어서 그다음으로 못생긴 수는 2가 된다. 이때 각각 2의 배수, 3의 배수, 5의 배수를 구하면 다음과 같다.

• 2의 배수: 2 x 2 = 4
• 3의 배수: 2 x 3 = 6
• 4의 배수: 2 x 4 = 8

이로써 우리는 4, 6, 8이 못생긴 수에 해당한다는 것을 알 수 있다. 따라서 이를 고려했을 때, 전체 못생긴 수는 {1, 2, 3, 4, 6, 8}이 된다. 이렇게 못생긴 수들을 작은 수부터 차례대로 확인하면서, 각 못생긴 수에 대해서 2,3,5의 배수를 고려한다는 점을 기억하여 효율적으로 소스코드를 작성하면 다음과 같이 작성 가능하다.

 

 

 

[소스코드 - 맞는코드]

 

n = int(input())

ugly = [0] * n # 못생긴 수를 담기 위한 테이블(1차원 DP 테이블)
ugly[0] = 1 # 첫 번째 못생긴 수는 1

# 2배, 3배, 5배를 위한 인덱스
i2 = i3 = i5 = 0
# 처음에 곱셈값을 초기화
next2, next3, next5 = 2, 3, 5

# 1부터 n까지의 못생긴 수를 찾기
for l in range(1, n):
    # 가능한 곱셈 결과 중에서 가장 작은 수를 선택
    ugly[l] = min(next2, next3, next5)
    # 인덱스에 따라서 곱셈 결과를 증가
    if ugly[l] == next2:
        i2 += 1
        next2 = ugly[i2] * 2
    if ugly[l] == next3:
        i3 += 1
        next3 = ugly[i3] * 3
    if ugly[l] == next5:
        i5 += 1
        next5 = ugly[i5] * 5
        
# n번째 못생긴 수를 출력
print(ugly[n - 1])

 

 

---

 

 

[처음 내가 푼 방법 - 틀린코드(예제만 맞음)]

# 못생긴 수

n = int(input())

result = [1]
i = 2
while len(result) < n+2:
    if not i % 2 or not i % 3 or not i % 5:
        if i % 7 == 0:
            i += 1
        else:  
            result.append(i)
            i+=1
    else:
        i+=1
        continue
print(result)
print(result[-1])

 

나의 경우에는 2,3,5로 나누어 떨어지는지 확인하고 7로 나누어 떨어지는 경우의 조건문을 별도로 설정후 쭉 진행하는 것이었다.

 

해당 코드는 2,3,5가 소인수가 될 수 없는 13의 배수인 26 등과 같은 부분이 예외처리가 가능하지 않아서 틀린 코드였다.

예제는 맞았지만 너무 헛점 투성이었다.

다시한번 생각해보니 7을 예외처리 한것처럼 계속 예외의 경우수가 생길경우에 대한 대비가 없었다.

 

'이코테'책의 풀이처럼 2,3,5만이 소인수가 될 수 밖에 없도록 각 수에 곱을 통한 방법이 옳은 답 같다.

 

가끔보면 역으로 생각해야 하는 경우가 많은 것 같다. 이해하는데 조금 헷갈렸다.

 

 

---

 

[통과]