[프로그래머스] 숫자 변환하기 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트

 

프로그래머스

 

1. 문제 설명

2. 풀이과정

해당 문제는 한 숫자의 다음 변환 결과가 총 3가지가 존재하므로 해당 경우의 결과를 전부 계산하고 그 값을 다음 계산에서 사용해야 한다.

처음에 deque 자료구조를 활용한 너비우선탐색 방법으로 해결해보려고 하였으나 몇몇 테스트에서 시간초과가 발생하였다. 하여 중복되는 계산을 최대한 없애려고 하였고 값을 저장하는 방식 list와 set으로 바꿔주었다.

 

1. 계산 결과를 저장할 2차원 리스트를 생성하고 초기 0행의 값은 x로 한다. li = [[x]]
2. 원하는 지점에서 종료하기 위해 무한 반복문을 사용한다. while (True)
3. 만약 가장 마지막 차례에 계산했던 값들 중 최종 변환 값이 있으면 if (y in li[-1])
4. 마지막 차례를 의미하는 횟수를 저장하고 answer = li.index(li[-1])
5. 값을 변환했으므로 종료한다. break
6. 종료되지 않았다면 값을 변환하고 저장할 세트를 생성한다. s = set()
7. 세트로 생성하는 이유는 값이 중복되는 것을 방지하여 동일한 계산을 줄이고자 함이다.
8. 가장 최근에 계산하여 저장된 값들을 하나씩 불러와 for i in li[-1]
9. 만약 해당 값에 n을 더했을 때 최종 변환 값보다 같거나 작으면 if (i + n <= y)
10. 해당 결과를 세트에 추가한다. s.add(i + n)
11. 만약에 해당 값에 2를 곱했을 때 최종 변환 값보다 같거나 작으면 if (i * 2 <= y)
12. 해당 결과를 세트에 추가한다. s.add(i * 2)
13. 만약에 해당 값에 3을 곱했을 때 최종 변환 값보다 같거나 작으면 if (i * 3 <= y)
14. 해당 결과를 세트에 추가한다. s.add(i * 3)
15. 모든 값의 다음 값을 계산한 다음, 만약 저장한 다음 값의 개수가 0개이면 if (len(s) == 0)
16. 최종 변환 값을 만들 수 없는 경우이므로 종료한다. break
17. 그게 아니라면 다음 값을 저장한 세트를 리스트에 추가한다. li.append(s)

반응형

3. 소스코드

def solution(x, y, n):
    answer = -1
    
    li = [[x]]
    while (True):
        if (y in li[-1]):
            answer = li.index(li[-1])
            break
            
        s = set()
        for i in li[-1]:
            if (i + n <= y):
                s.add(i + n)
            if (i * 2 <= y):
                s.add(i * 2)
            if (i * 3 <= y):
                s.add(i * 3)
        
        if (len(s) == 0):
            break
        li.append(s)

    return answer