[programmers] 숫자 변환하기

프로그래머스 Lv.2 숫자 변환하기

문제 분석
완전탐색 문제이다.
x,n,y가 주어지고 자연수 x를 y로 변환하려고 할 때, 다음 연산을 사용 가능하다.
1. x에 2를 곱하거나
2. x에 3을 곱하거나
3. x에 n을 더하거나

x를 y로 변환하는 데 필요한 최소 연산 횟수를 구하면 된다. (불가능할 경우 -1)

첫 번째 코드
길게 설명할 것 없이, 최단경로 문제로 간주하고 BFS 알고리즘을 구현하였다.

def solution(x, y, n):
    global count
    count = []
    BFS(x,n,0,y)
    if not count:
        return -1
    return min(count)


def BFS(x,n,c,y):
    queue = []
    queue.append((x,c))             # 현재 x와 c 값을 저장해준다.
    dx = [["*",2],["*",3],["+",n]]
    while queue:
        x,c = queue.pop()           # x와 c값을 큐에서 꺼낸다.
        c += 1                      # 작업을 할 것이므로 c를 1회 증가시켜준다.
        for i in dx:
            if i[0] == "*":
                x2 = x*i[1]
            elif i[0] == "+":
                x2 = x+i[1]
            if x2 > y:              # 이미 y값을 넘어가버렸으면 아무것도 추가하지 말고 break
                break               
            elif x2 == y:           # y값을 맞췄으면
                count.append(c)
            else:                   # 아직 y에 도달하지 않았으면, (x2,c)을 다시 큐에 넣고 반복한다.
                queue.append((x2,c))

첫 번째 코드 결과

음 일단 알고리즘을 구현하는 것 자체는 많이 익숙해졌다. 어느정도 원하는 대로 구현이 됐다.
하지만..

아... 시간초과도 있고 한 케이스는 심지어 오답으로 출력된다
먼저 생각나는 한 가지 경우에 대해 예외처리를 해 준다.
x2가 이미 탐색한 x를 다시 탐색하려 하는 경우를 없애기 위해서
visited 리스트를 선언하고, 방문한 x값을 visited에 추가한다.
x2가 visited 리스트에 존재하지 않는 경우에 대해서만 탐색을 진행한다.
코드는 크게 바뀐 것이 없으므로, 굳이 추가하지 않았다.

효율성이 일부 개선되었으나, 여전히 오답이 나오는 문항도 있고 효율성 문제가 아직 남아있다.
6번 테스트 케이스는 x == y 인 경우인것 같다. 문제 조건에 x<=y 인 점을 고려하여,

    if x == y:
        return 0

부분을 solution에 추가하여 예외처리 하였다.

몇 번째인지 모르겠는 코드
deque를 사용하고, bfs를 별도로 선언하지 않고 바로 solution에서 돌린다.

from collections import deque
def solution(x, y, n):
    if x == y:
        return 0
    queue = [x,0]
    queue = deque([queue])
    visited = []
    while queue:
        x,c = queue.popleft()
        c += 1
        visited.append(x)
        dx = [["*",2],["*",3],["+",n]]
        for i in dx:
            if i[0] == "*":
                x2 = x*i[1]
                if x2 == y:
                    return c
                elif x2 > y:
                    break
                else:
                    if x2 not in visited:
                        queue.append((x2,c))
            elif i[0] == "+":
                x2 = x+i[1]
                if x2 == y:
                    return c
                elif x2 > y:
                    break
                else:
                    if x2 not in visited:
                        queue.append((x2,c))
          
    return -1

실행 결과

그래도 많이 왔다.. 6번과 16번에 대한 예외처리가 완료 되었고 효율성도 많이 개선됐다.
근데 이제 진짜 뭘 줄여야 될 지 모르겠다.

또 새로운 코드
이번에는 dx를 for문을 돌리지 말고, 하나하나 해체해서 직접 연산해준다.
어차피 가장 적은 경로로 y에 도달하면 바로 return c가 시행될 것이기 때문에,
c를 큐에 담을 필요도 없고 비교할 필요도 없다.

def solution(x, y, n):
    if x == y:
        return 0
    queue = [(x, 0)]
    visited = set()
    while queue:
        x, c = queue.pop(0)
        c += 1
        visited.add(x)
        if x + n < y:
            if x+n not in visited:
                queue.append([x+n,c])
        elif x + n == y:
            return c
        if x*2 < y:
            if x*2 not in visited:
                queue.append([x*2,c])
        elif x*2 == y:
            return c
        if x*3 < y:
            if x*3 not in visited:
                queue.append([x*3,c])
        elif x*3 == y:
            return c
    return -1

실행 결과

지쳐간다. 점점 효율성은 좋아지고 있는데, 대체 무슨 테케를 넣어놓은걸까 이놈들은..
속는 셈 치고 queue를 deque로 선언 해보았다.

from collections import deque

queue = deque(queue)

x, c = queue.popleft()

하.... 9번 10번에 최대치가 들어있는 것 같다.
이제 진짜 뭘로 줄여야 하는거지?

도저히 더이상은 풀 수 없다고 판단되어 GPT에게 물어봤다.

새로 알게 된 스킬

from collections import defaultdict

그러니까 효율성 통과를 못 하던 이유는
이미 방문한 x를 검증하는 과정에서 더 효율적인 방법을 사용했어야 한다는 뜻인데,
이 defaultdict를 이용하면, "not in" 에 대한 검사를 안 해도 된다는 뜻이다.
너무 고마운 나머지 함수 이름을 import defaultdict as gomao 로 선언하였다.

제발 되라 코드

from collections import deque
from collections import defaultdict as gomao
def solution(x, y, n):
    if x == y:
        return 0
    queue = [(x, 0)]
    queue = deque(queue)
    visited = gomao(lambda : False)
    while queue:
        x, c = queue.popleft()
        c += 1
        if visited[x] == False:
            visited[x] = True
        else:
            continue  
        if x + n < y:
            queue.append([x+n,c])
        elif x + n == y:
            return c
        if x*2 < y:
            queue.append([x*2,c])
        elif x*2 == y:
            return c
        if x*3 < y:
            queue.append([x*3,c])
        elif x*3 == y:
            return c
    return -1

defaultdict의 사용법에 대해서는 GPT의 도움을 받았다.
그러니까, 기본값을 False(방문하지 않음)으로 defaultdict를 선언해 주고,
기본값이면 True로 변경(방문함)을 해주고
True(방문함) 이면 다시 반복문의 처음으로 돌아간다(이후 작업을 건너뛴다)

힘겹게 정답 처리를 받았다.
근데 defaultdict도 없고, deque도 없는 JavaScript로도 이 문제를 풀 수 있긴 할텐데
대체 어떻게 푸는지가 너무나도 궁금했다.

가 알고싶었는데....

다른 사람의 풀이

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

    while s:
        if y in s:
            return answer

        nxt = 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

진짜 왠만하면 다른 사람의 풀이에 충격 안 받는 편인데, 조금 충격 먹었다.
안 봐도 JavaScript로는 이렇게 풀었겠구나 싶다.
코드를 해석해보자.
1. 중복 불가능한 집합형 s를 선언하고, 최초 x값을 추가한다.
2. 반복문의 종료 조건을 설정한다. (y가 발견됨)
3. 다음 좌표를 집합형 nxt로 다시 선언하고,
4. 현재 집합에 들어있는 값을 사용해서 3가지 연산(+n, 2, 3)을 해준다.
5. 연산 결과를 nxt set에 추가한다. (중복은 자동으로 걸러진다)
6. nxt를 s에 덮어씌우고, 시행횟수를 1 증가시킨다.
7. 이 상태에서, 새로운 s를 조사하여 이미 y에 도달한 값이 있으면 answer을 즉시 반환한다.

놀랍다.

살짝 효율성은 진짜 미세하게 떨어지지만, 잡스킬 없이 깔끔하게 논리로 풀어낸 방법이다.
JavaScript 코드도 한 번 보고 넘어가자.

function solution(x, y, n) {
  if (x === y) return 0;
  const dp = {};
  dp[x] = 0;
  let data = [x];
  while (data.length) {
    const newData = [];
    for (const d of data) {
      for (const e of [d + n, d * 2, d * 3]) {
        if (e > y || dp[e]) continue;
        if (e === y) return dp[d] + 1;
        dp[e] = dp[d] + 1;
        newData.push(e);
      }
    }
    data = newData;
  }
  return -1;
}

이건 객체를 활용하여 파이썬의 defaultdict를 구현한 방법인것 같다.

function solution(x, y, n) {
    let count = 0
    let test = [x]

    if (x === y) return 0

    while (true) {
        count++

        const set = new Set()
        test.forEach(item => {
            if (item + n <= y) set.add(item + n)
            if (item * 2 <= y) set.add(item * 2)
            if (item * 3 <= y) set.add(item * 3)
        })

        if (set.size === 0) return -1

        if (set.has(y)) {
            return count
        }

        test = set
    }
}

이건 집합형을 이용하여 푼방법인것 같다.

객체로 푼 경우

집합형으로 푼 경우

심지어 더 효율적이다.

효율성 테스트를 확인해보느라 github가 난리 났다.

여러모로 많은 것을 느낀 문제였다.