[JS] 숫자 변환하기

 

 

난이도: Lv. 2

정답률: 55%

문제: https://school.programmers.co.kr/learn/courses/30/lessons/154538

프로그래머스

 

 

알고리즘

1. y보다 작기 때문에 정답 가능성이 있는 원소들을 possible에 저장한다.

2. possible에 있는 모든 원소에 대해 n을 더한 것, 2를 곱한 것, 3을 곱한 것이 정답 가능성이 있는지 확인하고, 정답 가능성이 있다면 새로운 possible 배열이 될 Set()에 저장한다.

3.  2.의 반복문이 끝나면 Set을 배열로 변환하여 possible로 지정한다.

위 과정을 possible 배열이 빌 때까지 반복한다. possible 배열이 빌 때까지 정답을 발견하지 못하면 x는 y가 될 수 없는 경우이므로 -1을 리턴한다.

 

정답 가능성이 있는 원소들이 각각 누적 레벨(몇 번 연산했는가)을 가지고 있는 것이 아니라 동일한 레밸의 모든 원소들에 대해 가능성을 확인하고 다음 레벨로 내려가는 형식이다.

 

 

코드

function solution(x, y, n) {
    var answer = 0;
    let possible = [x];

    while (possible.length) {
        const newPossibleSet = new Set();
        for (let e of possible) {
            if (e === y) { return answer; }

            if (e + n <= y) { newPossibleSet.add(e + n); }
            if (e * 2 <= y) { newPossibleSet.add(e * 2); }
            if (e * 3 <= y) { newPossibleSet.add(e * 3); }
        }

        possible = Array.from(newPossibleSet);
        answer++;
    }

    return -1;
}

 

 

주저리

처음에는 새로운 possible 배열 생성할 때 Set을 안 쓰고 그냥 배열로 해서 push 했는데 테케 9, 10에서 런타임 에러가 나고, 테케 5에서는 signal: aborted (core dumped)라는 에러가 발생했다. 검색해 보니까 배열이 너무 커서 메모리가 뻗은 거라고 한다. 아무리 생각해 봐도 이 방법밖에 없는데 대체 어떻게 푸는 것인가 하며 질문하기를 보니 BFS로 푼다길래 BFS로 풀었더니 시간초과가 나서 다시 질문하기를 보니 Set을 써야 한대서 BFS에서 Set을 추가해서 풀었는데 그래도 시간초과가 났다. 열받아서 처음에 했던 코드에 Set을 써서 풀었더니 풀렸다.