[C/C++] programmers Level 2 숫자 변환하기 - 참고

 

 

 

코드

 

#include <vector>
#include <queue> // 큐

using namespace std;

int solution(int x, int y, int n) {
    
    vector<int> visited(1000000,0); // 1<= x,y <= 1,000,000
    queue<pair<int, int>> q; // int : x에 *2,*3,+n 진행한 값 , int : 연산 횟수 
    
    if(x==y){ // x,y의 값이 시작부터 같은 경우 
        return 0;
    }else{
        q.push({x,0}); // int : x에 *2,*3,+n 진행한 값 , int : 연산 횟수 
    }
    // first : x에 *2,*3,+n 진행한 값, second : 연산 횟수 
    while(!q.empty()){
        auto Qnum=q.front(); // Qnum -> q값 저장
        q.pop();
        
        if(Qnum.first+n<=y && visited[Qnum.first+n]==0){ // n값을 더하고, n값을 더한 결과값이 처음 나왔을 경우 (첫 방문)
            visited[Qnum.first+n]++; // 방문 표시로 증감연산 
            
            if(Qnum.first+n==y){ // y값과 같아졌을 때 
                return Qnum.second+1; // 연산 횟수 증감 후 리턴 
            }else{
                q.push({Qnum.first+n,Qnum.second+1}); // 아닐 경우 연산한 값과 연산 회수 q에 삽입
            }    
        }
        
        if(Qnum.first*2<=y && visited[Qnum.first*2]==0){ // *2 연산 -> 위의 경우와 같은 패턴
            visited[Qnum.first*2]++;
            
            if(Qnum.first*2==y){
                return Qnum.second+1;
            }else{
                q.push({Qnum.first*2,Qnum.second+1});
            }    
        }
        
        if(Qnum.first*3<=y && visited[Qnum.first*3]==0){ // *3 연산 -> 위의 경우와 같은 패턴
            visited[Qnum.first*3]++;
            
            if(Qnum.first*3==y){
                return Qnum.second+1;
            }else{
                q.push({Qnum.first*3,Qnum.second+1});
            }    
        }
    }
    
    return -1; // x를 y로 변환할 수는 경우 -1 리턴
}