[Java] baekjoon_1107 : 리모컨

브루트포스 알고리즘

리모컨 : Gold5

https://www.acmicpc.net/problem/1107

1107번: 리모컨

 

 

풀이

import java.io.*;
import java.util.*;

public class Main {
  private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  private static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
  
  public static void main(String[] args) throws IOException {
    int N = Integer.parseInt(br.readLine());
    int M = Integer.parseInt(br.readLine());

    Set<Character> broken = new HashSet<>();
    if (M > 0) { // M이 0일 경우, 고장난 버튼이 없는 것이므로 if문 안의 코드는 실행될 필요 없다.
      String[] brokenButtons = br.readLine().split(" ");
      for (String button : brokenButtons) {
        broken.add(button.charAt(0));
      }
    }

    int ret = Math.abs(N - 100); // 100번 채널에서 현재 채널(N)로 이동하는 경우도 고려하기 위함이다.

    // N의 범위는 0 ≤ N ≤ 500,000 이지만, 
    // 9를 제외한 버튼이 모두 고장날 경우 999999를 눌러서 시작할 수도 있음을 고려했다.
    for (int i = 0; i <= 999999; i++) { 
      // 버튼 조작이 가능한 채널인 경우, 
      if (isPossible(i, broken)) {
        // 현재 계산된 조작 횟수(ret)와 해당 채널로 이동하는데 필요한 버튼 조작 횟수를 비교하여 최솟값을 갱신한다.
        ret = Math.min(ret, Integer.toString(i).length() + Math.abs(i - N));
      }
    }
    bw.write(ret + "\n");

    br.close();
    bw.close();
  }
  
 public static boolean isPossible(int c, Set<Character> broken) {
    for (char digit : Integer.toString(c).toCharArray()) {
      if (broken.contains(digit)) {
          return false;
      }
    }
    return true;
  }
}

 

 

이동하려는 채널 N (0 이상 500,000 이하)
고장난 버튼의 개수 M (0 이상 10 이하)
고장난 버튼의 번호가 주어집니다. (0부터 9까지의 정수)

ㄴ N의 최대값은 문제에서 500000이라고 되어있으나, 리모콘이 9를 제외하고 모두 고장났다면 999999를 눌러서 찾는 경우도 포함되어야 하므로 최대값을 999999으로 설정했다.
ㄴ 각 채널을 이동하기 위한 버튼 클릭 횟수를 계산한다.
    ㄴ 이때, 고장난 버튼을 누를 수 있는 경우를 제외하고 계산한다.
ㄴ 가능한 경우의 수를 탐색하기 위해 0부터 999,999까지의 모든 채널을 확인하고, 

ㄴ 해당 채널을 이동하기 위한 버튼 클릭 횟수를 계산한다. 

ㄴ 고장난 버튼을 사용할 수 없는 경우만 고려하며, 최소 횟수를 갱신한다.

=> 이렇게 각 채널에 대해 최소 횟수를 계산한 후,

최종적으로 이동하려는 채널로 이동하는 데 필요한 최소 버튼 클릭 횟수를 출력하도록 했다.

 

고장난 버튼 정보 저장하기

고장난 버튼의 번호를 HashSet에 저장했다.

HashSet을 사용하는 이유는 중복된 값을 효율적으로 처리하기 위함이다.

 

초기값 설정

초기값으로 현재 채널에서 목표 채널까지의 거리를 계산한다.

이는 |목표 채널 - 현재 채널| 값이다.

가능한 경우의 수 탐색

가능한 경우의 수를 탐색하기 위해 0부터 999,999까지의 모든 채널을 확인한다.
isPossible 메서드를 사용하여 고장난 버튼을 사용할 수 있는 경우를 제외하고 계산한다.
가능한 경우의 수를 모두 계산하고, 그 중에서 최소한의 버튼 클릭 횟수를 찾는다.
최종적으로 최소한의 버튼 클릭 횟수를 출력한다.

isPossible 메서드

isPossible 메서드는 주어진 숫자를 만들기 위해 고장난 버튼을 사용할 수 있는지 여부를 확인한다.
숫자를 문자열로 변환한 후, 각 자리의 숫자가 고장난 버튼에 포함되어 있는지 확인한다.