[1107] 리모컨
문제 분석
요약해보자면.......
채널 이 주어진다.
+, - 버튼으로 채널을 ±1 할 수 있다.
0 ~ 9 버튼 중 고장 난 버튼 이 주어진다.
몇 번만에 해당 채널 을 찾을 수 있는지 최솟값을 리턴하라.
시작 채널 은 100 번이다.
고장나지 않은 버튼이 주어질 수 있다.
이동하기 위한 채널은 0 <= N <= 500,000 이다.
풀이 과정
🎯 시작 채널 은 100 번이다.
주어진 채널(이동해야 할 채널) 이 100 인 경우 0 을 출력하고 종료한다.
if (findChannel == 100) {
System.out.println(0);
return;
}🎯 +, - 버튼으로만 이동하는 경우
(주어진 채널 - 100) 은 +, - 버튼으로만 채널을 이동한 결괏값이 된다. (절댓값 기준)
아래처럼 결괏값에 미리 담아준 후에, 고장 난 버튼 으로 이동하는 최솟값과 비교할 것이다.
int result = Math.abs(100 - findChannel);🎯 고장난 버튼으로 이동하는 경우
예제 1을 보자.
5457 로 이동해야하고, 6, 7, 8 버튼이 고장났다.
고장나지 않은 버튼들을 조합해 가장 가까운 위치로 이동하는 경우의 수는 2개다.
5455 로 이동이 가능하고, 5459 로 이동이 가능하다.
해당 위치에서 +, - 버튼을 2번 누르면 5457 로 이동이 가능하여, 총 6 회 클릭이다.
🎯 고장난 버튼을 체크해줄 배열을 만든다.
버튼은 총 0 ~ 9 까지. 때문에 배열의 사이즈를 10으로 설정.
boolean[] errerButton = new boolean[10];예제 1 기준으로 현재 배열은 이렇게 설정이 되어있다. (boolean 기본값은 false 다)
errorButton[6] = true, errorButton[7] = true, errorButton[8] = true
🎯 고장난 버튼으로 갈 수 있는 채널인지? 아닌지?
매개변수로 주어지는 채널을 문자열로 바꾼다음 확인하는 메서드다.
무엇을 확인하냐면 리모컨 버튼으로 갈 수 있는지, 없는지를 확인한다.
errorButton[] 배열에는 0~9 까지의 버튼 중 고장난 버튼들이 ture 로 설정되어있다.
private static int check(String number) {
int length = number.length();
for (int i = 0; i < length; i++) {
char check = number.charAt(i);
if (errerButton[check - '0']) {
return -1;
}
}
return Integer.parseInt(number);
}이 메서드에서 -1 이 리턴된다는 뜻은 고장난 버튼들 때문에 이동할 수 없다는 뜻.
그게 아니라면 이동할 수 있다는 뜻인데, 버튼 클릭 횟수는 채널의 길이와 같다.
ex ) 1234 로 이동이 가능하다면 버튼을 4 회 누르면 된다. (1234 가 문자열일 경우 길이가 곧 횟수)
ex ) 82 로 이동이 가능하다면 버튼을 2 회 누르면 된다. (82 가 문자열일 경우 길이가 곧 횟수)
🎯 매개변수로 어떤 숫자들을 주면서 확인할 거냐? 가장 가까운 수를 어떻게 찾느냐?
찾지 않고 모든 경우의 수를 다 추가할 것이다.
이동해야할 채널은 0 <= N <= 500,000 50만 번의 for 문을 돌리면 된다. 나쁘지 않다.
하지만 주의해야 할 점이 있다.
찾아야 할 채널의 최댓값은 500,000 이지만 이동할 수 있는 채널은 그 이상도 가능하다.
극단적인 예제로..
ex ) 500,000 번으로 채널을 이동하기 위해
800,000 에서 한 칸씩 - 버튼을 눌러가며 도착하는 횟수가 100 에서 시작하는 횟수보다 더 빠르다.
for 문으로 0 에서 부터 1,000,000 까지의 경우의 수를 모두 확인 한다.
🎯 핵심 로직
for (int i = 0; i <= 1_000_000; i++) {
String number = Integer.toString(i);
int check = check(number);
if (check == -1) continue;
...
}0 부터 1,000,000까지 찾아야할 경우의 수 채널을 문자열로 바꿔준다.check()메서드를 통해 리모컨 버튼으로 이동할 수 있는지 확인한다.- 이동할 수 없다면
-1이 리턴되므로continue; - 아니라면.......
...
if (check == -1) continue;
int cal = Math.abs(findChannel - check);
result = Math.min(result, cal + number.length());
...- 아니라면 아래의 로직이 실행된다.
이동하고자 하는 채널 - check는 버튼을 눌러서 이동하게될 값이다.
예제 1을 기준으로 이동하고자 하는 채널은5457
5455or5459를 문자열로 변환에 매개변수로 넣으면,
check()메서드에서 나온 값은5455or5459이 된다.
5457-5455or5457-5459의 값은 절댓값으로2가 된다.
int cal에2가 담긴다.
즉, 리모컨 버튼으로 근처까지 이동한 다음에,+, -버튼으로 몇 번 눌러야이동하고자 하는 채널로 도착하는지의 값이다.- 문자열의 길이가 버튼 클릭 횟수가 된다.
5455or5459는4가 된다. 이동하고자 하는 채널로 이동하는 최소 횟수는 마지막 문자열의 길이를 더해준2 + 4 = 6이 되고 기존에 담겨져있던 최솟값(오로지+, -버튼으로만 이동하는 경우) 와 비교하여 변수에 담아준다.
나의 생각
처음에 무언가 규칙이 있을 것 같아서 DP 로 접근하였다가 망했다.
주어지는 이동해야 할 채널 의 범위가 넓지 않아서 완전 탐색으로 바꾸었지만 쩔쩔맸다..
결국 블로그 글들을 통해 핵심 로직을 알게 되었다.
문제에 대해 접근할 때 조금 더 세부 로직으로 나누어서 생각한다면 단순해지는 것 같다.
코드
package baekjooncompletion;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class BaekJoon1107 {
private static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
private static final boolean[] errerButton = new boolean[10];
public static void main(String[] args) throws IOException {
int findChannel = Integer.parseInt(br.readLine());
int caseSize = Integer.parseInt(br.readLine());
if (caseSize > 0) {
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i = 0; i < caseSize; i++) {
errerButton[Integer.parseInt(st.nextToken())] = true;
}
}
if (findChannel == 100) {
System.out.println(0);
return;
}
int result = Math.abs(100 - findChannel);
for (int i = 0; i <= 1_000_000; i++) {
String number = Integer.toString(i);
int check = check(number);
if (check == -1) continue;
int cal = Math.abs(findChannel - check);
result = Math.min(result, cal + number.length());
}
System.out.println(result);
}
private static int check(String number) {
int length = number.length();
for (int i = 0; i < length; i++) {
char check = number.charAt(i);
if (errerButton[check - '0']) {
return -1;
}
}
return Integer.parseInt(number);
}
}
