[프로그래머스][C++] 숫자 변환하기

숫자 변환하기

문제 링크

숫자 변환하기

분석

DFS를 사용하면 시간 초과가 납니다.

최소 연산 횟수를 구하는 문제이므로 BFS(너비 우선 탐색)를 사용하면 최적의 해를 찾을 수 있습니다.
한 번 방문한 숫자는 다시 방문할 필요가 없습니다.
BFS는 “최단 거리” 문제를 푸는 데 적합합니다.

큐(Queue)를 사용하여 현재 숫자에서 가능한 모든 연산을 수행하면서 최소 횟수를 찾을 수 있습니다.

과정은 다음과 같습니다.

1. 시작 숫자 x에서 시작합니다.
2. x에 가능한 연산을 적용하여 y에 도달하는지를 확인합니다.
3. 중복 탐색을 방지하기 위해 방문한 숫자는 저장해 둡니다.
4. y에 도달하면 지금까지의 연산 횟수를 반환합니다.
5. 모든 경우를 탐색했음에도 y에 도달하지 못하면 -1을 반환합니다.

풀이

#include <vector>
#include <queue>
#include <unordered_set>

using namespace std;

int solution(int x, int y, int n) {
    // x와 y가 같은 경우
    if (x == y) return 0;
    
    queue<pair<int, int>> queue;    // 현재 숫자와 연산 횟수를 저장
    unordered_set<int> set; // 연산 했던 숫자 저장
    
    // 첫 연산 값 지정
    set.insert(x);
    queue.push({x, 0});
    
    // queue가 비어있게 될때까지
    while (!queue.empty())
    {
        // 현재 숫자와 현재 연산 횟수를 가져옴
        int currentNum = queue.front().first;
        int currentCount = queue.front().second;
        
        // queue에서 제거
        queue.pop();
        
        // 연산 수행
        int nextValues[] = {currentNum + n, currentNum * 2, currentNum * 3};
        
        // 연산의 결과 순회
        for (int nextVal : nextValues)
        {
            // 연산의 결과가 y와 같은 경우
            if (nextVal == y)
            {
                // 연산 횟수 반환
                return currentCount + 1;
            }
            
            // 연산의 결과가 y보다 작고, 연산 했던 적 없는 숫자인 경우
            if (nextVal < y && set.find(nextVal) == set.end())
            {
                queue.push({nextVal, currentCount + 1});
                set.insert(nextVal);
            }
        }
    }
    
    // y를 만들 수 없는 경우
    return -1;
}

성능 요약

시간 복잡도는 $O(y)$입니다.

• BFS를 통한 연산 횟수 $O(3(y - x)) \approx O(y - x) \approx O(y)$

공간 복잡도는 $O(y)$입니다.

• 중복된 숫자를 제외하고 탐색할 숫자를 저장하는 queue $O(y - x)$
• 연산 했던 숫자를 저장하는 set $O(y - x)$
• $O(y - x + y - x) = O(2(y − x)) \approx O(y)$

테스트 1 〉 통과 (0.02ms, 4.23MB)
테스트 2 〉 통과 (0.01ms, 4.17MB)
테스트 3 〉 통과 (0.01ms, 4.17MB)
테스트 4 〉 통과 (0.01ms, 4.16MB)
테스트 5 〉 통과 (12.41ms, 7.11MB)
테스트 6 〉 통과 (0.01ms, 4.21MB)
테스트 7 〉 통과 (12.14ms, 7.17MB)
테스트 8 〉 통과 (0.01ms, 4.01MB)
테스트 9 〉 통과 (103.73ms, 23MB)
테스트 10 〉 통과 (75.09ms, 20.7MB)
테스트 11 〉 통과 (29.47ms, 11.2MB)
테스트 12 〉 통과 (0.01ms, 4.23MB)
테스트 13 〉 통과 (0.01ms, 4.13MB)
테스트 14 〉 통과 (0.48ms, 4.23MB)
테스트 15 〉 통과 (0.06ms, 3.65MB)
테스트 16 〉 통과 (0.17ms, 4.01MB)