[BOJ] 1107 - 리모컨 (Java)

알고리즘

• 브루트포스 알고리즘

1. 문제

• 특정 채널로 이동하기 위해 고장난 버튼을 피하면서 가장 적게 버튼을 누르는 것이 목적

2. Idea

• broken 함수로 고장난 리모콘 버튼을 체크

• 고장나지 않은 리모콘 버튼으로만 target과 가장 근사한 번호를 만든 후 +, - 로 이동하는 값 중의 최소값을 선택

• 이때 target과 가장 근사한 번호는 그냥 0번부터 최대값까지 모든 번호를 다 누르고 +, -로 이동한 다음 그 중의 최소값을 선택한다. (완전탐색문제)

• 최댓값은 문제에서 500000이라고 되어있으나 리모콘이 9를 제외하고 모두 고장났다면 999999를 눌러서 찾는 경우도 포함되어야 하므로 최대값을 999999으로 설정한다.

• 이제 0부터 999999까지 숫자를 늘려가면서 번호가 고장나지 않은 번호를 눌러서 표현할 수 있으므로, 그 번호에서 +, -로 값을 찾을때 리모콘을 누르는 횟수를 계산하여 그리고 값 중에서 최소값을 반환한다.

3. 풀이

3.1. 변수 입력

• target: 이동하려는 채널
• m: 고장난 버튼의 개수

Scanner scan = new Scanner(System.in);

int target = scan.nextInt(); // 이동하려는 채널
int m = scan.nextInt(); // 고장난 버튼의 개수

3.2. 고장난 버튼 처리

• 고장난 버튼의 정보를 받아서 해당 버튼이 고장났는지를 나타내는 배열 broken에 저장

boolean[] broken = new boolean[10];
for (int i = 0; i < m; i++) {
    int n = scan.nextInt();
    broken[n] = true;
}

3.3. 이동 및 고장난 버튼 처리 및 결과 출력

• 초기값 result를 현재 위치에서 100번 채널까지 이동하는 횟수로 설정
• 0부터 999999까지의 모든 가능한 채널에 대해 고장난 버튼을 피하면서 이동하는 횟수를 계산
• 각 채널의 숫자를 문자열로 변환하여 각 자릿수에 대해 고장난 버튼 여부를 확인하고, 만약 고장난 버튼을 눌러야 하는 경우에는 해당 숫자를 무시하고 다음 채널로 넘어간다.
• 고장난 버튼을 피하면서 이동하는 횟수를 계산하고, 현재까지의 최소 이동 횟수(result)보다 작으면 업데이트

int result = Math.abs(target - 100); // 초기값 설정
for (int i = 0; i <= 999999; i++) {
    String str = String.valueOf(i);
    int len = str.length();
    
    boolean isBreak = false;
    for (int j = 0; j < len; j++) {
        if (broken[str.charAt(j) - '0']) {
            isBreak = true;
            break;
        }
    }
    if (!isBreak) {
        int min = Math.abs(target - i) + len;
        result = Math.min(min, result);
    }
}

System.out.println(result); // 최종적으로 계산된 최소 이동 횟수를 출력

4. 전체코드

import java.util.*;
 
public class Main {    
    
    public static void main(String[] args)  {
        Scanner scan = new Scanner(System.in);
        
        int target = scan.nextInt();
        int m = scan.nextInt();
        
        boolean[] broken = new boolean[10];
        for(int i = 0; i < m; i++) {
            int n = scan.nextInt();
            broken[n] = true;
        }
        
        int result = Math.abs(target - 100); //초기값 설정
        for(int i = 0; i <= 999999; i++) {
            String str = String.valueOf(i);
            int len = str.length();
            
            boolean isBreak = false;
            for(int j = 0; j < len; j++) {
                if(broken[str.charAt(j) - '0']) { //고장난 버튼을 눌러야 하면
                    isBreak = true; 
                    break; //더 이상 탐색하지 않고 빠져나온다.
                }
            }
            if(!isBreak) { //i를 누를때 고장난 버튼을 누르지 않는다면
                int min = Math.abs(target - i) + len; //i를 누른 후(len) target까지 이동하는 횟수(target - i)
                result = Math.min(min, result);
            }
        }        
        System.out.println(result);
    }
}