다시푸는 코딩 테스트 준비 일지
문제
정수 A를 B로 바꾸려고 한다. 가능한 연산은 다음과 같은 두 가지이다.
2를 곱한다.
1을 수의 가장 오른쪽에 추가한다.
A를 B로 바꾸는데 필요한 연산의 최솟값을 구해보자.
입력
첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다.
출력
A를 B로 바꾸는데 필요한 연산의 최솟값에 1을 더한 값을 출력한다. 만들 수 없는 경우에는 -1을 출력한다.
예제 입력 1 복사
2 162
예제 출력 1 복사
5
2 → 4 → 8 → 81 → 162
예제 입력 2 복사
4 42
예제 출력 2 복사
-1
예제 입력 3 복사
100 40021
예제 출력 3 복사
5
100 → 200 → 2001 → 4002 → 40021
문제 풀이 접근
이 문제는, 일반적인 BFS 를 maps 형식으로 구성할 수 있게 주는 문제가 아니었다.
원리는 같은데 발상이 다른 느낌이어서 조금 고민해보고 어떻게 풀지 가닥을 잡았다.
다른 BFS,DFS 문제는 맵을주로 상하좌우를 탐색하지만 원리는 같고, 오히려 이게 더 이쪽 원리에서 더 기초적인 방법이지 않을까? 라는게 내 생각이다.
masp[,] 와 같은 2차원 배열이 아닌 행동으로 나타내기 때문이다.
BFS의 원리인 Queue들 돌면서 약간의 그리디 알고리즘 키워드가 들어가 있는것을 알았는데,
내가 만든 숫자와 타겟 숫자가 같다고 판단되면 다른 경로는 모두 신경쓰지 않고, 바로 종료하도록 하며, 타겟 숫자보다 넘어갈 경우 enqueue 를 하지 않도록 하였다.
그리고 이 문제의 유의점 3가지가 있다.
둘다 내가 잘못읽은 것이지만, 이것 때문에 시간을 오래썼으므로 남긴다.
첫번째는, 2번 액션에서 우측에 '1' 을 추가한다 라는 지문인데,
예를들면 20 일때 21 이 아닌 201 이 되는 것이다.
두번째는, target의 수 범위다. 10의 9승이면 10억이다. 여기서 정수의 표현범위를 알면 내가 말하고자 하는 의미를 알 수 있을 것이라고 생각한다.
마지막으로, 가장 나를 괴롭혔던 문제인데, 10의 9승 즉 10억이기 때문에 1바이트라도 배열을 세워서 거기에 값 남기고 이렇게하면 메모리초과에서 절대로 헤어나올 수 없다.
이 세가지만 유의하면 금방 풀럴 것이다
정답 작성 코드 (C#)
using System;
using System.CodeDom;
using System.Collections.Generic;
using System.ComponentModel;
using System.ComponentModel.Design;
using System.Diagnostics;
using System.IO;
using System.Linq;
using System.Runtime.CompilerServices;
using System.Runtime.InteropServices;
using System.Security.AccessControl;
using System.Security.Authentication;
using System.Security.Cryptography;
using System.Security.Cryptography.X509Certificates;
using System.Text;
using System.Threading;
using System.Threading.Tasks;
using System.Web;
using System.Xml.Linq;
using static CodingTestProj.Program;
/*
* Difficulty : Middle
* URL : https://www.acmicpc.net/problem/16953
*/
namespace CodingTestProj
{
internal class Program
{
static void Main(string[] args)
{
//Case 0 _ Short
Solution solution = new Solution();
solution.solve();
}
}
public class Solution
{
public int start;
public double target;
public double ret;
public Dictionary<double, double> dic;
public void solve()
{
dic = new Dictionary<double, double>();
string[] input = Console.ReadLine().Split(' ');
start = Convert.ToInt32(input[0].ToString());
target = Convert.ToInt64(input[1].ToString());
BFS();
Print();
}
public void BFS()
{
Queue<double> q = new Queue<double>();
q.Enqueue(start);
if (dic.ContainsKey(start) == false)
dic.Add(start, 1);
while (q.Count > 0)
{
var cur = q.Dequeue();
if (cur == target)
break;
if (cur > target)
continue;
var calc1 = (double)cur * (double)2;
var calc2 = double.Parse(cur.ToString() + "1");
if (calc1 <= target)
{
q.Enqueue(calc1);
if (dic.ContainsKey(calc1) == false)
{
var values = dic[cur] + 1;
dic.Add(calc1, values);
}
}
if (calc1 == target)
break;
if (calc2 <= target)
{
q.Enqueue(calc2);
if (dic.ContainsKey(calc2) == false)
{
var values = dic[cur] + 1;
dic.Add(calc2, values);
}
}
if (calc2 == target)
break;
}
}
public void Print()
{
ret = dic.ContainsKey(target) == false ? (double)(-1) : dic[target];
Console.WriteLine(ret);
}
}
}코드 결과
이 문제를 풂으로써, 등급이 S4가 되었다.