[PS] 백준 1107 리모컨 java 풀이

1107번: 리모컨

처음 문제 접근

• BFS인가? 하기엔 시도해야할 경우의 수가 너무 많은 것 같다. 사실상 브루트 포스로 하게 될 듯
• 채널이 0 ≤ N ≤ 500,000니까 배열에 각 최소 횟수를 업데이트 해주는 식으로 해야할 것 같음
• 고장이 안난 리모컨 배열에서 입력할 수 있는 모든 경우의 수를 만들어야 하나? 그럼 백트래킹인가?
• 그럼 for문을 언제까지 돌리고 언제 끝내야하지?

답지 보고 문제 접근

1. 먼저 리모컨 배열을 만든다. 

이 배열에 값이 -1이면 고장난 것을 의미한다.

        int n = Integer.parseInt(br.readLine());
        if (n != 0) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int i = 0; i < n; i++) {
                int idx = Integer.parseInt(st.nextToken());
                remote[idx] = -1;
            }
        }

2. 리모컨으로 만들 수 있는 채널인지 검사하는 함수 구현

 static int canPress(int channel) {
        if (channel == 0) {
            return (remote[0] == -1) ? 0 : 1;
        }

        int length = 0;
        while (channel > 0) {
            if (remote[channel % 10] == -1) {
                return 0;
            }
            length += 1;
            channel /= 10;
        }
        return length;
    }

• 목표 채널이 0 채널이고, 0이 고장 안 났으면 1, 고장났으면 0 리턴 (왜냐하면, 리모컨으로 만들 수 없으므로)
• 채널의 값을 10으로 나눠가면서, 각 자릿수가 이미 리모컨에서 고장난 숫자라면 만들 수 없으므로 0 리턴, 만들 수 있으면 length + 1
• 예를 들어, 목표 채널이 5457이고 모두 고장이 안 났다면 4번 누를 수 있으므로 4 리턴

3. 0부터 넉넉히 1,000,000 까지 모든 채널을 검사하여 목표 채널에 도달할 수 있는 횟수 업데이트

        int minPresses = Math.abs(target - 100);
        for (int channel = 0; channel <= 1000000; channel++) {
            int length = canPress(channel);
            if (length > 0) {
                int presses = length + Math.abs(channel - target);
                if (presses < minPresses) {
                    minPresses = presses;
                }
            }
            
        }

        System.out.println(minPresses);

• 시작은 100부터 이므로 최소 누른 횟수는 (목표 채널 - 100) 이는 모든 리모컨이 고장나서 + 또는 -로만 눌러야 하는 횟수를 의미
• 현재 for 문으로 순회하는 채널이 리모컨으로 만들 수 있는 채널인지 체크
• 만들 수 있다면 리모컨을 누른 횟수 +  abs(현재 채널 - 목표 채널) 로 최소 횟수 계산
• 예를 들어 5457이고, 고장난 버튼이 6, 7, 8인 경우 channel = 5455 일 때 canPress에서 4를 리턴 받겠고, 
  abs(5455 - 5457) = 2 이므로 4+2 = 6임

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    static int[] remote = new int[10];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int target = Integer.parseInt(br.readLine());

        int n = Integer.parseInt(br.readLine());
        if (n != 0) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int i = 0; i < n; i++) {
                int idx = Integer.parseInt(st.nextToken());
                remote[idx] = -1;
            }
        }

        int minPresses = Math.abs(target - 100);
        for (int channel = 0; channel <= 1000000; channel++) {
            int length = canPress(channel);
            if (length > 0) {
                int presses = length + Math.abs(channel - target);
                if (presses < minPresses) {
                    minPresses = presses;
                }
            }
            
        }

        System.out.println(minPresses);

    }

    static int canPress(int channel) {
        if (channel == 0) {
            return (remote[0] == -1) ? 0 : 1;
        }

        int length = 0;
        while (channel > 0) {
            if (remote[channel % 10] == -1) {
                return 0;
            }
            length += 1;
            channel /= 10;
        }
        return length;
    }

}

느낀점

처음 문제 접근을 보면... 모든 경우의 수를 검사하돼 검사 하는 방식에 대해 도저히 감이 안 왔다..

배열을 500,001 사이즈로 만들어서 모든 리모컨으로 만들 수 있는 경우의 수를 만든 다음에, 각 경우의 수 부터 시작해서 배열 값들을 업데이트 해야하나.. 이런 식으로 떠올렸다.

 

정답은 리모컨을 누를 수 있는지 판별 후, 리모컨 누른 횟수 + (현재 채널 - 목표 채널) << 이 식으로 푸는 것 이었다.

 

코테는 정말... 많이 풀어봐야 하는 것 같다.