백준 1107. 리모컨

문제 링크

난이도	정답률(_%)
Gold 5	22.276%

설계

• 이동하려고 하는 채널 번호 N 최대 500,000
• 고장난 버튼의 개수 M 최대 10
• 처음엔 채널에 고장난 버튼이 포함될 경우 제일 가까운 채널로 이동해 + - 식으로 이동하려고 했지만 가정해야할 상황이 너무 많고, 제일 가까운 채널을 찾아내는 조건도 너무 까다로워서 포기
• 경우의 수가 너무 많아서 그냥 다 해보는 것이 낫겠다고 생각해서 모든 순회하면서 가장 이동횟수가 적은 채널을 찾도록 했다.

시간 복잡도

• 888888번 채널까지 순회하면서 고장난 버튼이 있는지 확인하는 로직
• O(888888 * 10) = O(N)

공간 복잡도

• 고장난 버튼인지 표시하는 boolean 형 배열 길이 10
• 각 채널을 순회하면서 char 형으로 변환된 배열 최대 6자리

풀이

• 채널 0번 ~ 채널 888888번까지 순회한다.
  • 순회하면서 해당 채널에 고장난 버튼이 있으면 그냥 넘어간다.
  • 고장난 버튼이 없다면 버튼을 누른 횟수를 계산해서 최소 횟수와 비교해 교체한다.

처음엔 999999번까지 순회하도록 했는데, 다른 사람들 코드를 보니 888888번까지만 순회하도록 하고 있었다.

왜 999999번까진 확인하지 않는지 가장 큰 채널을 기준으로 확인해보니, 500000번 채널로 이동할 때 [0, 1, 2, 3, 4, 5, 6, 7]번 버튼이 고장났을 경우 888888번이 가장 가까운 채널이고, [0, 1, 2, 3, 4, 5, 6, 7, 8]번 버튼이 고장나면 99999, 900000번이 가장 가까운 채널로 888888번 안에 모든 계산이 끝난다는 것을 확인할 수 있었다.

결과

메모리	실행 시간
91164KB	276ms

999999번까지 가도록 했을 때

메모리	실행 시간
100796KB	284ms

코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

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

        int finalChannel = Integer.parseInt(br.readLine());
        int brokenButtonCount = Integer.parseInt(br.readLine());
        boolean[] brokenButtons = new boolean[10];

        if (brokenButtonCount > 0) {
            for (String button : br.readLine().split(" ")) {
                brokenButtons[Integer.parseInt(button)] = true;
            }
        }

        int minimalMoving = Math.abs(finalChannel - 100);

        for (int i = 0; i <= 888888; i++) {
            char[] currentChannel = String.valueOf(i).toCharArray();

            if (!canPressChannelButton(brokenButtons, currentChannel)) {
                continue;
            }

            if (minimalMoving > Math.abs(i - finalChannel) + currentChannel.length) {
                minimalMoving = Math.abs(i - finalChannel) + currentChannel.length;
            }
        }

        bw.write(Integer.toString(minimalMoving));

        bw.flush();
        bw.close();
    }

    public static boolean canPressChannelButton(boolean[] buttons, char[] channel) {
        for (char number : channel) {
            if (buttons[number - '0']) {
                return false;
            }
        }

        return true;
    }
}