2024년 11월 8일 TIL

 

위의 문제를 거진 5일 정도 고민을 한 것 같다...

 

function solution(x, y, n) {
    let result = -1;
    function dfs(value, num)
    {
        if(value === y)
        {
            if(result === -1 || result > num) result = num
            return
        }
        else if(value > y) return
        
        dfs(value + n, num + 1)
        dfs(value * 3, num + 1)
        dfs(value * 2, num + 1)
    }
    dfs(x,0)
    return result;
}

처음에는 dfs 방식으로 재귀 함수를 이용해 초기값 x가 

 

x + n

x * 2

x * 3

 

(향후 x + n, x * 2, x * 3은 매개변수에 의해 value가 된다)

 

이 될 때 마다 count인 num을 1씩 증가시키는 방식으로

 

value가 y와 같아지는 경우를 찾고 그때 num이 최솟값이 되는 경우를 찾고자 했다. 그 결과,

 

실패(런타임 에러)인 stackOverFlow가 발생하는 경우가 존재했고,

실패(시간 초과)로 제한 시간에 걸리는 경우가 존재했다.

 

며칠을 방법을 생각해보다 stackOverFlow가 발생하지 않게 하기 위해

반복문을 사용하기로 결정하고, 반복에 따른 시간을 최소화 시키기 위해 JavaScritp의

Set 인스턴스를 사용하기로 결정했다.

(Set은 중복을 제거한 배열형식으로 요소들을 저장한다.)

 

 그렇게 작성된 코드가

 

function solution(x, y, n) {
    if(x === y) return 0
    let set = new Set([x + n, x * 2, x * 3])
    let temp = []
    let count = 1;
    while(true)
    {
        if(set.has(y)) break;
        count++;
        for(let value of set)
        {
            if(value + n <= y) temp.push(value + n)
            if(value * 2 <= y) temp.push(value * 2)
            if(value * 3 <= y) temp.push(value * 3)
        }
        if(temp.length === 0) return -1;
        set.clear();
        set = new Set(temp)
        temp = []
    }
    return count;
}

 

먼저,

    if(x === y) return 0

으로 x가 y일 경우 +n, * 2, * 3을 수행할 필요가 없기 때문에 return 0을 해야했다. 그 후,

 

new Set으로 먼저 x + n, x * 2, x * 3을 Set의 인스턴스에 담아줬다.

 

그리고 while문 안에서 먼저,

 

if(set.has(y))

 

로 Set인스턴스에 찾고자 하는 y가 존재할 경우 break문으로 while문을 탈출할 수 있게 해줬고,

존재하지 않으면 

        for(let value of set)
        {
            if(value + n <= y) temp.push(value + n)
            if(value * 2 <= y) temp.push(value * 2)
            if(value * 3 <= y) temp.push(value * 3)
        }

Set 인스턴스에서 값(value)를 순차적으로 가져와

 

value + n

value * 2

value * 3

 

한 값이 y보다 작거나 같을 경우 빈 배열 temp에 담아줬다.

 

이때, 배열에는 아무 값도 저장이 되지 않을 수 있는데

해당 경우는 Set 인스턴스에 요소가 모두 y보다 큰 경우가 되므로

 

초기값 x가 y가 될 수 있는 경우가 존재하지 않음을 의미하기 때문에

 

        if(temp.length === 0) return -1;

 

return -1로 함수 종료 및 반환을 시켜줬다.

 

다른 경우로, 배열에 값이 존재할 경우

 

        set.clear();
        set = new Set(temp)
        temp = []

 

set.clear()로 Set 인스턴스를 모두 제거해줬고,

다시 set  = new Set(temp)로 배열의 모든 요소를 set 인스턴스에 넣어줬다.

 

이때 set.add(...temp)가 아닌 set = new Set(temp)를 한 이유는 

 

set.add(...temp)는 단일 값을 추가하기 위한 함수이기 때문에 value + n만 저장되는 문제가 존재했다.

그래서, set = new Set(temp)로 배열의 요소들을 Set 인스턴스에 넣을 수 있게 해줬다. 

 

그 결과,

 

어떤 경우에 수행시간이 긴 경우가 존재했지만, 모든 테스트 케이스를 통과할 수 있었다.

 

향후, 문제를 푼 다른 방식들을 찾아 보던 중 내가 작성한 코드가 BFS 방식으로 넓이 우선 탐색이였다는 사실을 알게 됐다.

 

BFS는 DFS와 다르게

 

 

왼쪽 BFS, 오른쪽 DFS (출처 : https://developer-mac.tistory.com/64)

Branch(가지)를 우선 탐색하는 방식이었다.

 

( DFS는 Depth(깊이)를 우선 탐색하는 방식이다.)