코딩테스트 : 숫자 변환하기

해당 문제는 원하는 숫자를 가장 빠른게 찾는 문제로 주어진 규칙을 가지고 원하는 숫자를 빠르게 찾는 알고리즘을 만들어야한다.

첫 번째 시도

#include <string>
#include <vector>
#include <queue>

using namespace std;

int solution(int x, int y, int n) {
    int answer = 0;
    
    //int : 현재 연산 값, int : 연산 횟수
    queue<pair<int, int>> q;
    //초기 값 x, 연산 횟수는 없으니 0
    q.push(make_pair(x, 0));
    
    //q에 원소가 없을때까지 같은게 안 나왔다면 값이 없다는 뜻
    while(!q.empty())
    {
		    //같은 값이 나왔다면
        if(q.front().first == y)
		        //연산 횟수를 반환
            return q.front().second;
        //y보다 크다면 연산에서 제외
        if(q.front().first > y)
            q.pop();
        //같지 않고 y보다 작다면 + n, *2, *3의 경우를 q에 넣어서 이후 연산
        else if(q.front().first < y)
        {
            q.push(make_pair(q.front().first + n, q.front().second + 1));
            q.push(make_pair(q.front().first * 2, q.front().second + 1));
            q.push(make_pair(q.front().first * 3, q.front().second + 1));
            q.pop();
        }
    }
    
    return -1;
}

중복된 값을 계속 큐에 넣고 연산하기 때문에 시간 초과 문제가 발생한다.

이후 중복된 값을 자동으로 걸러주는 자료구조인 set을 이용해 중복된 값이면 연산하지 않게 구현한다.

두 번째 시도

#include <string>
#include <vector>
#include <queue>
#include <set>

using namespace std;

int solution(int x, int y, int n) {
    int answer = 0;
    
    //int : 현재 연산 값, int : 연산 횟수
    queue<pair<int, int>> q;
     //초기 값 x, 연산 횟수는 없으니 0
    q.push(make_pair(x, 0));
    //중복 값을 걸러주기 위한 set 선언
    set<int> s;
    //초기 값 넣기
    s.insert(x);
    
    //q에 원소가 없을때까지 같은게 안 나왔다면 값이 없다는 뜻
    while(!q.empty())
    {
		    //현재 값을 저장
        int current = q.front().first;
        //현재 값에 대한 연산 횟수를 저장
        int step = q.front().second;
        
        //현재 값 q에서 제거
        q.pop();
        
        //현재 값이 y라면
        if(current == y)
		        //현재 값에 대한 연산 횟수 반환
            return step;
        
        //연산은 3가지 경우로 반복되므로 저장 후 반복문
        int value[3] = {current + n, current * 2, current * 3};
        
        for(int i : value)
        {
		        //연산 결과가 y보다 작거나 같으면서 set에 저장되어있지 않다면(중복처리)
            if(i <= y && s.find(i) == s.end())
            {
		            //다음 q에 연산 결과 넣기
                q.push(make_pair(i, step + 1));
                //중복 값 검사를 위해 set에 값 추가
                s.insert(i);
            }
        }
        
    }
    
    return -1;
}

위 코드 처럼 set을 이용하면 손 쉽게 중복된 값을 구별할 수 있으며, 이를 제거해주며 시간 초과 문제를 해결할 수 있다.