Unity 내일배움캠프 TIL 1011 | 프로그래머스 숫자 변환하기

컨디션 난조 + 아이디어 고갈 + 귀찮음

3단 콤보로 이번 개인 프로젝트는 게임 로직을 분석해보기로 했다 ,,

근데 이제 진행된게 없는

그래서 오늘도 알고리즘 리뷰 ^v^

숫자 변환하기

문제

자연수 x에 1. n을 더하거나 2. 2를 곱하거나 3. 3을 곱해서 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와 y의 값은 정수의 범위를 넘지 않는다
2. 3가지 연산 중 하나를 선택하고, 또 그 뒤에 하나를 선택하면서 완전 탐색을 해야 할 것 같다
3. 완전 탐색은 DFS

시도

• 처음엔 DFS로 풀어보았으나, 테스트 케이스의 반은 통과하고 반은 시간 초과가 났다.
  재귀의 깊이 때문에 그런 것 같다!!!

풀이

• 최소 횟수는 최단 거리와도 같기 때문에 BFS로 풀었다.
  보통 visited 배열로 체크하던 방문 여부는 HashSet으로 바꿨다.
  이미 만들어진 값인지 아닌지 체크하는 용도
  이미 만들어진 값이라면 최소 횟수는 이미 체크가 되었기 때문에, HashSet에 값이 없을 때만 추가하면 된다!
• 풀이 코드

using System;
using System.Collections.Generic;

public class Solution {
    static int result;
    public int solution(int x, int y, int n)
    {
        result = -1;

        bfs(x, y, n);

        int answer = result;
        return answer;
    }

    static void bfs(int x, int y, int n)
    {
        Queue<int[]> queue = new Queue<int[]>();
        HashSet<int> set = new HashSet<int>();

        queue.Enqueue(new int[] { x, 0 });

        while (queue.Count > 0)
        {
            int[] cur = queue.Dequeue();
            int curNum = cur[0];
            int curCnt = cur[1];

            if (curNum == y)
            {
                result = curCnt;
                return;
            }

            for (int i = 0; i < 3; i++)
            {
                int nextNum = 0;
                switch (i)
                {
                    case 0: nextNum = curNum + n; break;
                    case 1: nextNum = curNum * 2; break;
                    case 2: nextNum = curNum* 3; break;
                }

                if (nextNum <= y && !set.Contains(nextNum))
                {
                    queue.Enqueue(new int[] { nextNum, curCnt + 1 });
                    set.Add(nextNum);
                }
            }
        }
    }
}

다른 해결법

• 문제를 해결 후 질문하기 게시판을 떠돌다가 발견한 진짜 쏘 지니어스한 발상
  현재는 x에서 y를 만드는 상향식 방법을 사용하는데, y에서 x를 도출해내는 하향식 방법으로 답을 구하면 훨씬 빠르게 구할 수 있다고 한다.
• x + n, 2x, 3x는 모두 정수가 되지만, y - n, y/2, y/3은 float가 될 수도 있기 때문에 정수가 되는 경우만 걸러내면 경우의 수가 훨씬 줄어들기 때문!!!
  진짜 이런 생각은 어떻게 하는거지????
• DP로도 풀이할 수 있는 것 같아서 나중에 한 번 더 시도해봐야겠다!

야근 할 생각에 신이 나요

이게 다 내 업보...그래요....

끗..