C# 숫자 변환하기 - BFS / 프로그래머스 [Lv.2]

출처: 프로그래머스 코딩 테스트 연습
https://school.programmers.co.kr/learn/courses/30/lessons/154538

 

 

나의 코드

using System;
using System.Linq;
using System.Collections.Generic;

public class Solution 
{
    public int solution(int x, int y, int n) 
    {
        var open = new HashSet<int>();
        var openOther = new HashSet<int>();
        var close = new HashSet<int>();
        int count = 0;
        
        open.Add(x);
        
        while(open.Count > 0)
        {
            if(open.Contains(y))
                return count;
            
            ++count;
            openOther.Clear();
            foreach(var num in open)
            {
                close.Add(num);
                
                int a = num + n;
                if(a <= y && !close.Contains(a))
                    openOther.Add(a);

                int b = num * 2;
                if(b <= y && !close.Contains(b))
                    openOther.Add(b);
                
                int c = num * 3;
                if(c <= y && !close.Contains(c))
                    openOther.Add(c);
            }
            
            var temp = open;
            open = openOther;
            openOther = temp;
        }
        
        return -1;
    }
}

처음에는 두개의 리스트를 사용해서

num + n / num * 2 / num * 3 을 각각 구해서 openOther 리스트에 넣고,

open 리스트와 openOther 리스트를 스왑하는 방식으로 구현했다.

 

테스트는 통과했지만 시간 초과.

n이 1인 경우, n을 더해서 num * 2이나 num * 3과 값이 같아지는 경우 중복해서 구하기 때문에 초과되는 것.

 

중복수를 배제하는 것이 첫 문제였으니 hashSet을 사용해서 open 숫자들을 관리하기로했다.

추가로 계산의 결과가 이미 검증을 거친 수가 나올 수 있으니 close 숫자를 관리하는 hashSet도 선언.

 

 

추가적으로 생각해보면

별도로 숫자마다 해당 숫자에 도달할때까지의 횟수를 저장하는 배열을 선언해서

다익스트라 방식으로 구해볼 수도 있을 것같다.