프로그래머스 2023.09.06 (2Lv 숫자 변환하기)

프로그래머스

문제

---

문제 설명
자연수 x를 y로 변환하려고 합니다. 사용할 수 있는 연산은 다음과 같습니다.
  ◈ x에 n을 더합니다
  ◈ x에 2를 곱합니다.
  ◈ x에 3을 곱합니다.
자연수 x, y, n이 매개변수로 주어질 때, x를 y로 변환하기 위해 필요한 최소 연산 횟수를 return하도록 solution 함수를 완성해주세요. 이때 x를 y로 만들 수 없다면 -1을 return 해주세요.

제한사항
  ◈ 1 ≤ x ≤ y ≤ 1,000,000
  ◈ 1 ≤ n < y

입출력 예

x	y	n	result
10	40	5	2
10	40	30	1
2	5	4	-1

입출력 예 설명
입출력 예 #1
x에 2를 2번 곱하면 40이 되고 이때가 최소 횟수입니다.

입출력 예 #2
x에 n인 30을 1번 더하면 40이 되고 이때가 최소 횟수입니다.

입출력 예 #3
x를 y로 변환할 수 없기 때문에 -1을 return합니다.

코딩

---

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

using namespace std;

struct tNode
{
    int     iNum = 0;
    bool    bFind = false;
    int     iCount = 0;
};

tNode BFS(int _iX, int _iY, int _iN)
{
    tNode tNowNode = {};

    queue<tNode> queue = {};
    
    tNowNode.bFind = false;
    tNowNode.iCount = 0;
    tNowNode.iNum = _iY;

    queue.push(tNowNode);

    while (!queue.empty())
    {
        tNowNode = queue.front();
        queue.pop();

        if (tNowNode.iNum == _iX)
        {
            tNowNode.bFind = true;
            break;
        }
        else if (tNowNode.iNum != _iX)
        {
            tNowNode.iCount += 1;

            int iPrevNum = tNowNode.iNum;
            if (iPrevNum % 2 == 0 && iPrevNum / 2 >= _iX)
            {
                tNowNode.iNum = iPrevNum / 2;
                queue.push(tNowNode);
            }

            if (iPrevNum % 3 == 0 && iPrevNum / 3 >= _iX)
            {
                tNowNode.iNum = iPrevNum / 3;
                queue.push(tNowNode);
            }

            if (iPrevNum - _iN >= _iX)
            {
                tNowNode.iNum = iPrevNum - _iN;
                queue.push(tNowNode);
            }
        }
    }
    
    return tNowNode;
}

int solution(int x, int y, int n) {
    int answer = 0;

    tNode tResult = BFS(x, y, n);

    if (tResult.bFind)
    {
        answer = tResult.iCount;
    }
    else
    {
        answer = -1;
    }

    return answer;
}

처음 문제를 풀때, BFS를 떠올리지 못했다. 단순히 재귀함수를 구현해서 하나하나 찾아보려했지만, 그럴 경우 시간초과할 것이 분명했지만 우선 구현을 하다가 짜던 코드를 보니 BFS를 이용할 수 도 있겠다는 생각이 들었다.

 

BFS를 이용해서 구현했을 때, 기본으로 주어지는 예제는 모두 통과했으나, 시간 초과가 걸렸다.

애초에 방문 체크를 하지 않아도 시간 초과로 인한 실패는 잘 없지 않을까 하는 마음에 하지 않았던게 컸던 것 같다.

 

하지만 방문 체크를 해서 통과하더라도 보다 시간을 단축할 수 있지 않을까 하는 생각에 찾아보니, 수를 X에서 시작해 탐색하지 않고, Y에서 시작해 X가 되는 것을 찾는 탐색이 훨씬 시간이 적게 걸린다는 것을 알게 되었다.

 

방문 체크는 단순히 같은 수를 다시 반복하지 않는 것에 그치지만, Y에서 시작해 X를 찾는 방식은 Y % 2나 Y % 3의 결과가 0이 아니라면 가지치기를 할 수 있기 때문이다. 2나 3으로 수를 나누었을 때, 나머지가 0이 아니라는 것은 2나 3을 계속해 곱해도 Y라는 수가 나올 수 없다는 것이기 때문이다.

 

이전부터 반복문이나 알고리즘의 시작을 뒤에서 할 생각을 하지 않아서 시간 초과가 걸리는 경우가 더러 있었다.

앞으로는 반대로 접근하면 어떻게 되는지에 대해 더 고민을 해보고 문제를 풀어야 할 것 같다.

 

실행 결과

---