BruteForceSearch 백준 알고리즘 자바 1107 ‘리모컨’ 문제풀이

Problem

수빈이는 TV를 보고 있다. 수빈이는 채널을 돌리려고 했지만, 버튼을 너무 세게 누르는 바람에, 일부 숫자 버튼이 고장났다. 리모컨에는 버튼이 0부터 9까지 숫자, +와 -가 있다. +를 누르면 현재 보고있는 채널에서 +1된 채널로 이동하고, -를 누르면 -1된 채널로 이동한다. 채널 0에서 -를 누른 경우에는 채널이 변하지 않고, 채널은 무한대 만큼 있다. 수빈이가 지금 이동하려고 하는 채널은 N이다. 어떤 버튼이 고장났는지 주어졌을 때, 채널 N으로 이동하기 위해서 버튼을 최소 몇 번 눌러야하는지 구하는 프로그램을 작성하시오. 수빈이가 지금 보고 있는 채널은 100번이다.

Input 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼이 주어지며, 같은 버튼이 여러번 주어지는 경우는 없다.

Output 첫째 줄에 채널 N으로 이동하기 위해 버튼을 최소 몇 번 눌러야 하는지를 출력한다.

Solution

완전 탐색 정말 완전 힘들다. 많은 블로거분들의 도움을 받아 문제를 해결하였다. 특히, https://appree.tistory.com/7 감사합니다.

• list.contains()를 사용하기 위해 입력 받는 고장난 번호를 ‘리스트’에 저장한다. 배열을 쓰시는 분도 많았다.
• 채널 100부터 시작하므로 100에서 원하는 채널까지 +키 또는 -키만으로 이동했을 때의 횟수를 최솟값 min에 저장한다. 절대값을 구하는 Math.abs()사용!
• 이동하려고 하는 채널이 0부터 50만까지이다. 밑에서부터 위로 50만까지 갈 수도 있지만, 위에서부터 밑으로 50만까지 갈 수 있으므로 0부터 100만까지의 모든 숫자를 확인한다. for(int i = 0; i <= 1000000; i++)
• 임의로 만든 채널 i가 버튼 조작으로 이동 가능한지 메서드 chk()로 확인한다.
• 채널를 숫자 하나하나 쪼개어 생각해보아야 한다. 예를 들어 274번으로 이동하고 싶은데 고장난 번호 리스트에 2가 있는지 7이 있는지 4가 있는지 확인해야 하기 때문이다. (num % 10을 하면 처음에 1의 자리 숫자가 나오고, 그 뒤에 num /= 10을 해서 또 %연산을 하면 최초의 num의 10의 자리 숫자가 나온다.)
• 만약 고장난 번호키이면 해당 채널은 숫자키를 눌러 움직일 수 없다는 의미로 0을 반환한다.
• 그게 아니면 각 버튼을 누른 횟수 length를 하나씩 증가시켜 최종적으로 length 변수 값을 반환한다.
• 채널이 0일 때는 %연산이 안 되므로 따로 빼서 처리했다.
• 이동하고 싶은 채널 chanel 에서 지금 임의로 구한 채널 i를 빼면, i부터 + 또는 - 키로 움직이는 횟수가 나온다. 여기에 i를 가기 위해 눌렀던 버튼 입력 횟수를 더해준 것이 지금까지 구한 방법보다 적은지 아닌지 비교해 최솟값을 구한다.

Code

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class Main {
	static List<Integer> list = new ArrayList<>();
	
	private static int chk(int num) {
		int length = 0;
		if(num == 0) return list.contains(num)? 0 : 1;
		
		while(num > 0) {
			if(list.contains(num % 10)) return 0;
			
			length++;
			num /= 10;
		}
		return length;
	}
	
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int chanel = scan.nextInt(), m = scan.nextInt();
		
		while(m-- > 0) list.add(scan.nextInt());
		
		int min = Math.abs(chanel - 100);
		for(int i = 0; i <= 1000000; i++) {			
      int length = chk(i);
      
			if(length > 0) min = Math.min(min, Math.abs(chanel - i) + length);
		}
		System.out.print(min);
	}
}