사실 비슷한 문제를 백준에서 풀어보았습니다.
이 문제는 올림을 어떻게 처리할 것인가를 생각했다면 쉽게 풀었을거 같습니다.
하지만 저는 BFS로 접근하자고 생각했습니다.
문제에서 주어진 수가 1 ≤ storey ≤ 100,000,000
이었기 때문에 시간 초과가 발생했습니다.
BFS는 모든 경우의 수를 생각하기 때문입니다.
따라서 문제를 다시 읽어보면 한가지 힌트가 있습니다.
바로 4일 경우에는 -1씩 4번 버튼을 누르는 것이 이득이지만
6일 경우에는 +1씩 4번 버튼을 눌러서 10으로 만들고 -10의 버튼을 누르는 것이 이득입니다.
아래와 같은 흐름으로 갑니다
storey = ⏺️⏺️⏺️⏺️
4자리의 수라고 가정할 때
엘리베이터와 같이 1의 자리 숫자부터 접근합니다.
현재 엘리베이터에서 빼야하는 자리의 층수 = storey%10;
남은 엘리베이터 층수= storey = storey/10;
storey가 0이 아닐때까지 반복
근데 문제를 풀다보니 몇 개의 테스트 케이스에서 실패라고 떠서 왜 뜨는지 원인을 찾아보았습니다.
3가지 경우로 생각해봐야 하는것을 깨달았습니다.
위의 조건을 모두 만족하도록 풀이를 구현했습니다.
시간초과가 발생한 풀이와 올림 방식을 활용한 두 개의 풀이를 다음과 같이 정리합니다.
import java.util.*;
class Solution {
static int result =Integer.MAX_VALUE;
static int max=0;
public int solution(int storey) {
int answer = 0;
// 절대값이 10의 c승
// 더한 결과가 0보다 작은 경우에는 움직이지 않는다.
// 버튼 1번당 마법의 돌 한개
// 마법의 돌을 적게 사용하는 방법
//BFS인데 어떻게 저 많은 수를 고르냐에 문제
//1. storey의 자릿수를 구한다.
//2. 그 자리의 반복은 0부터 시작하여 list에 넣고
//3. 그 값에 따라 BFS 진행
//1번 과정
int length = Integer.toString(storey).length();
//2번 과정
ArrayList<Integer> list = new ArrayList<>();
// 엘리베이터에서 누를 수 있는 모든 버튼
for(int i=0;i<=length;i++){
int input = (int)(Math.pow(10,i));
list.add(input);
list.add(-1*input);
}
//단위
int t = (int)(Math.pow(10,length-1));
// 앞 자리
int index = storey%t==0? storey/t: storey/t +1;
max= index*t;
//0부터 20까지
boolean[] visited = new boolean[max+1];
System.out.println(index*t);
bfs(storey,list,visited);
return result;
}
// 엘리베이터 버튼을 활용하여 0을 만들 수 있는 모든 경우의 수
static void bfs(int storey, ArrayList<Integer> list, boolean[] visited){
Queue<int[]> q = new LinkedList<>();
q.offer(new int[]{storey,0});
visited[storey]=true;
while(!q.isEmpty()){
int[] output = q.poll();
if(output[0]==0){
if(result>output[1])
result = output[1];
}
for(int l : list){
if( output[0]+l>=0 && output[0]+l<=max && !visited[output[0]+l]){
visited[output[0]+l]=true;
q.offer(new int[]{output[0]+l,output[1]+1});
}
}
}
}
}
import java.util.*;
class Solution {
public int solution(int storey) {
int answer = 0;
while(storey!=0){
// 마지막 숫자
int at = storey%10;
// 그 다음 남은 수
storey=storey/10;
// 마지막 숫자가 5보다 크거나 같은 경우
if(at>5) {
// 연산의 횟수에 더하기
answer+=10-at;
// 앞자리 수 바뀌기
storey+=1;
}else if(at<5){
// 연산의 횟수에 더하기
answer+=at;
// at가 5인 경우
}else{
if(storey%10>=5){
answer+=10-at;
storey+=1;
}else{
answer+=at;
}
}
}
return answer;
}
}