[알고리즘] 숫자 변환

Lv. 2

간단해 보였지만, while x=y: 정도밖에 생각을 못했다

정답 풀이 구현을 보고 놀람.

정답 풀이

def solution(x, y, n):
    answer = 0
    s = set()
    s.add(x)
    
    while s:
        if y in s:
            return answer

        nxt = set()  # new set
        for i in s:
            if i+n <= y:
                nxt.add(i+n)
            if i*2 <= y:
                nxt.add(i*2)
            if i*3 <= y:
                nxt.add(i*3)
                
        s = nxt
        answer+=1

    return -1

1. target 값인 y가 s안에 있을 때까지 돈다.

2. nxt라는 새로운 set을 만들어주고, 이 안에는 세 종류의 연산으로 구해지는 값을 넣는다.

3. s는 nxt로 update된다.

 

nxt set에서는 가능한 모든 연산값이 중복되지 않게 저장된다. 이 안에 target과 일치하는 값이 있다면? 종료하면 됨. 그리고 그 때의 연산 횟수 return.

 

출처: 프로그래머스 코딩 테스트 연습, https://school.programmers.co.kr/learn/challenges