백준(BOJ) 1107 : 리모컨 (JAVA)

문제링크 : https://www.acmicpc.net/problem/1107

1107번: 리모컨

낮은 정답률(현재 21%)에 비해 비교적 쉬운 문제다. 물론 필자도 처음 이 문제를 풀 때 엄청 헤맸다...;;; '아놔 그냥 리모컨 고쳐 쓰지 왜 망가진 걸 쓰고 난리야'라고 한탄하면서 풀었던 기억이 난다ㅋㅋㅋ 풀이에 대한 설명을 하자면

 

1. 망가지지 않은 버튼으로 누를 수 있는 채널 중 N과 가장 가까운, N보다 큰 값 upperNo를 구한다. 

   : 버튼을 누른 횟수 = upperNo의 길이 + (upperNo - N)

2. 망가지지 않은 버튼으로 누를 수 있는 채널 중 N과 가장 가까운, N보다 작은 값 lowerNo를 구한다.

   : 버튼을 누른 횟수 = lowerNo의 길이 + (N - lowerNo)

3. +, - 버튼으로만 이동

   : 버튼을 누른 횟수 = N - 100 의 절대값

 

이 3개의 값 중 가장 작은 값을 구하면 된다. 다들 여기까진 쉽게 생각을 할 것 같다. 문제는 1, 2번을 구하는 방법인데, 처음에는 어떻게든 규칙성을 찾으려고 발악을 했으나... 분기가 너무 많았다. 근데 생각을 해보자. 그냥 1씩 더하거나 빼면서 upperNo, lowerNo를 구할 때의 시간복잡도는 얼마일까? O(N)이다. 그냥 N... 아놔... 코드는 아래와같다.

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.StringTokenizer;
 
public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int m = Integer.parseInt(br.readLine());
        
        if(m > 0) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            boolean[] broken = new boolean[10];
            
            for(int i = 0; i < m; i++) { 
                broken[Integer.parseInt(st.nextToken())] = true;
            }
            
            List<Integer> candidates = new ArrayList<Integer>();
            candidates.add(Math.abs(n - 100));
            
            int upperNo = getUpperNo(n, broken);
            int lowerNo = getLowerNo(n, broken);
            
            if(upperNo != -1) {
                candidates.add(String.valueOf(upperNo).length() + upperNo - n);
            }
            
            if(lowerNo != -1) {
                candidates.add(String.valueOf(lowerNo).length() + n - lowerNo);
            }
            
            Collections.sort(candidates);
            
            System.out.println(candidates.get(0));
        } else {
            System.out.println(Math.min(Math.abs(n - 100), String.valueOf(n).length()));
        }    
    }
    
    private static int getUpperNo(int n, boolean[] broken) {
        boolean allBrokenExceptZero = true;
        
        for(int i = 1; i < 10; i++) {
            if(!broken[i]) {
                allBrokenExceptZero = false;
                break;
            }
        }
        
        if(allBrokenExceptZero) {
            return -1;
        }
        
        while(n < 1000_000) {
            if(isPossible(n, broken)) {
                return n;
            }
            
            n++;
        }
        
        return -1;
    }
    
    private static int getLowerNo(int n, boolean[] broken) {
        boolean allBroken = true;
        
        for(int i = 0; i < 10; i++) {
            if(!broken[i]) {
                allBroken = false;
                break;
            }
        }
        
        if(allBroken) {
            return -1;
        }
        
        while(n >= 0) {
            
            if(isPossible(n, broken)) {
                return n;
            }
            
            n--;
        }
        
        return -1;
    }
    
    private static boolean isPossible(int n, boolean[] broken) {
        if(n == 0) {
            return !broken[0];
        }
        
        while(n > 0) {
            int tmp = n % 10;
            n /= 10;
            
            if(broken[tmp]) {
                return false;
            }
        }
        
        return true;
    }
}

몇 가지를 더 설명하자면, upperNo와 lowerNo가 절대 나올 수 없는 경우가 있다. 이 경우에는 아예 비교 대상에서 제외를 시켜야하는데, upperNo의 경우 1~9까지 모두 망가졌을 경우, lowerNo의 경우 모든 숫자 버튼이 망가졌을 경우에 나올 수 없다. 그 밖에도 N이 5인데 0~4까지 다 망가졌을 경우도 있을 수 있고 upperNo가 1,000,000보다 커질 경우에는 비교의 의미가 없다(N의 최대값이 500,000인데 +버튼만 이용해도 499,900번 누르면 갈 수 있기 때문)