Lv2. 숫자 변환하기

문제 보기 :  숫자 변환하기

프로그래머스

 

---

문제

• 정답률 : 57%

---

작성 코드

def solution(x, y, n):
    answer = 0
    an = [x]
    if x == y:
        return 0
    
    while y not in an:
        a = [] ; answer += 1
        for i in an:
            j = [i+n,i*2,i*3]
            if y in j:
                return answer
            else:
                a += j
        # a = [i for i in a if i<y]
        if min(a) > y :# if len(a) == 0:
            return -1
        else:
            an = a
    return answer

100점 만점에 75점,,,

응 다시할게요,.

def solution(x, y, n):
    answer = 0
    an = [x]
    if x == y:
        return 0
    
    already = {} ; already2 = {i+1:[] for i in range(1000)}
    while y not in an:
        answer += 1
        for i in an:
            # j = [i-n,i/2,i/3]
            if i+n not in already and x<i+n<y:
                already[i+n]=answer
                already2[answer].append(i+n)
            elif i+n==y:
                return answer
            
            if i*2 not in already and x<i*2<y:
                already[i*2]=answer
                already2[answer].append(i*2)
            elif i*2==y:
                return answer
            
            if i*3 not in already and x<i*3<y:
                already[i*3]=answer
                already2[answer].append(i*3)
            elif i*3==y:
                return answer
                
        a = already2[answer]
        if len(a) == 0:
            return -1
        else:
            an = a
    return answer

---

풀이

시간초과가 지인짜 문제인 문제다.

근데 1:1 매칭이 되는 딕셔너리로 풀면 바로 되더라..

전에는 중복으로 나오는 숫자도 모두 포함되게.. 그니까 다시 말해서 앞서 나왔던 숫자도 다시 계산되도록 알고리즘을 짰다

예를 들어, x=15, y=100, n=5라면 [x+n, x*2, x*3]으로 계속 계산이 되는거니까, [20, 30, 45] - [25, 40, 60, 35, 60, 90, 50, 90, 135] - [30, 50, 75, 45, 80, 120, 65, 120, 180... 55, 100, 150, 95, 180, 270, 140, 270, 405] 이렇게 짰는데 이렇게 하면 중복되는 값이 많아져서 시간초과가 생긴다.

그래서 already라는 딕셔너리로 앞서 나온 값들은 계산하지 않도록 했다. already2는 answer를 key로 두고 an을 업데이트 시키는 딕셔너리다.

예시로 설명하자면 x=15, y=100, n=5의 경우 already에 i+n=20이 없다면 추가, already2[1]에 추가.
i*2=30도 똑같이 실행. i*3=45도 똑같이 실행한다.

an = already[1] = [20, 30, 45]로 업데이트

그리고 i가 20이고 i*3=60일 때, already에 추가. already[2]에도 추가한다. 근데 i가 30, i*2=60일 때, already는 이미 있으니 추가 안하고, already[2]에도 추가하지 않는다. 
대소관계 비교도 추가해서 y를 초과하는 값은 already, already2에 추가하지 않는다.