[java]리모컨 - 백준1107

문제

• 리모컨(백준1107)

풀이

문제 해석을 하자면,

• 리모컨의 버튼이 0~9 와 +,- 가 존재한다고 가정한다.
• 이때, 고장난 버튼들이 입력으로 주어지면 해당 버튼은 사용못한다.
• 이 상태에서 입력받은 채널 N 으로 이동할때 버튼을 최소 몇 번 눌러야 하는가?
• 단, 수빈이는 현재 채널 100번에 머물러있다.

풀이

• 가장 가까운 수를 택하는것을 “브루트포스” 로 구하자.
• • “이분탐색”으로 처음에 하려고 했는데 오히려 안풀릴 것 같다.
  • 힌트를 보니 그냥 브루트포스! (시간초과가 안나나보네??)
• 가장 가까운 수를 택할 때 “중복 순열” 로 접근했다.
• 전체 흐름
  • 사용가능 버튼 찾기
  • (1) 채널 100에서 +,- 이동했을 때
  • (2) 0~9 숫자입력으로 채널 이동 후 +,- 이동했을 때
  • (출력) 둘 중에 더 작은 수를 사용
• 주의 : 예외를 잘 처리해야한다
  • 입력값의 길이를 N이라 할 때 가장 가까운 수의 길이가 N-1, N, N+1 이 될 수 있다는것을 꼭 알고 풀어야한다.
  • 해당 반례 때문에 한참 시간 낭비ㅜㅜ

/*
반례 참고 -> N-1, N+1

0
3
0 1 2
output : 4 (N-1 길이의 예)

999
2
9 8
output : 5 (N+1 길이의 예)
*/

코드

static String input;
static int M, uSize;
static int[] breakBtn; // 고장난 버튼
static int[] usedBtn; // 사용가능한 버튼
static int[] outArr;
static int minDiff = Integer.MAX_VALUE;
static int minDiffLen;

public static void main(String[] args) throws IOException {
    StringBuilder sb = new StringBuilder();
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    input = br.readLine();
    M = Integer.parseInt(br.readLine());
    breakBtn = new int[M + 1];
    if(M!=0) {
        StringTokenizer stk = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < M; i++) {
            breakBtn[i] = Integer.parseInt(stk.nextToken());
        }
    }
    //run
    //find -> 사용가능 버튼 찾기
    findBtn();
    //(1) 100에서 +,- 이동했을 때
    int result1 = find100();
    //(2) 0~9 숫자 이동후 +,- 이동했을 때
    int result2 = find0N9();
    //output
    System.out.println(Math.min(result1, result2));
}

// N-1, N, N+1 일 때를 고려해서 구현했기에 조건문이 다소 복잡하다.
// 범위가 N-1 "이상" 이고 N+1 "이하" 들을 outArr(=`가장 가까운 수`) 로 사용하는것으로 구현했다.
private static void dfs(int depth) {
    //base condition
    if ((input.length()-1>0 && depth >= input.length()-1) ||
        (input.length()-1==0 && depth >= input.length())) {
        int findNum = 0;
        for (int i = 0; i < depth; i++) {
            findNum += + outArr[i]*(int) Math.pow(10,i); // outArr -> 숫자로 변환
        }
        //debug
        //      System.out.println(findNum);
        int num = Integer.parseInt(input); // 입력값(원본)
        int findNumLen = String.valueOf(findNum).length(); // findNum 자리수
        minDiff = Math.min(minDiff, Math.abs(num - findNum) + findNumLen);
        if (depth == input.length()+1) return; //탈출시점
    }
    //recursion -> 중복 순열
    for (int i=0; i<uSize; i++) {
        outArr[depth] = usedBtn[i];
        dfs(depth + 1);
    }
}

private static int find0N9() {
    outArr = new int[7]; // 최대 1,000,000 까지 가까운 수 택 가능하므로 7자리로 설정
    dfs(0);
    int diff = minDiff;
    return diff;
}

private static int find100() {
    int inNum = Integer.parseInt(input);
    int diff = Math.abs(inNum - 100);
    return diff;
}

static void findBtn() {
    usedBtn = new int[10];
    boolean[] vis = new boolean[10]; // 방문배열로 고장난 버튼 판별
    for (int i = 0; i < M; i++) {
        vis[breakBtn[i]] = true;
    }
    int idx=0;
    for (int i = 0; i <= 9; i++) {
        if(vis[i]) continue;
        usedBtn[idx++] = i;
    }
    uSize = idx;
}

느낀점

1년 전에 제출기록이 있어서 확인해보니 이 코드보다 훨씬 짧게 구현했던 기록이 있다.

아마 그때는 구글링을 해서 다른사람의 코드를 참고했었던것 같다.

지금 코드는 너무 난해하지만 스스로 풀었다는것에 만족..!