백준 1107 리모컨 Java

정답률 22퍼센트인 리모컨문제이다.

문제 자체가 어렵진 않지만 생각보다 고려해야 하는 요소가 많아서

정답까지 도달하려면 제출을 많이 해봐야 되는 것 같다 .. 그래서 22퍼센트 같다.

 

현재 채널은 100이고

가고싶은 채널 n이 주어지며

리모컨에서 고장난 버튼이 주어진다.

 

n채널에 가기위해 눌러야 하는 리모컨 버튼의 횟수를 출력하면 되는 문제이다.

 

예를 들어 고장난 버튼이 없을 때 2000이 가고 싶으면

2 0 0 0 을 리모컨으로 눌러서 4를 출력하면 된다.

 

처음엔 별 생각없이 n에서 한자리씩 떼어서 고장나지 않은 버튼과의 차이를

절대값으로 계산해서 가장 작은 차이로 바꾸는 식으로 문제를 풀었다.

 

하지만 틀렸습니다가 계속해서 나와 답답한 마음에

질문 게시판에 들어갔는데 

이 반례하나에 다 수정하게 되었다.

1555

8

0 1 3 4 5 6 7 9

내가 계산한 방법으로 하면

가장 가까운 수는 2222가 되고

2222에서 1555로 가기위해 -버튼을 667회 누르고

2222를 가기위해 눌렀던 버튼횟수 4회를 더한

671을 출력하는데

정답은 670이다.

 

어떻게 670이냐면 가장 가까운 수를 888로 하고

888에서 1555로 가기위한 667회와

888을 가기위한 3회를 더해서

670이었다.

 

888이란 수는 내가 작성한 코드에서는 n을 한자리씩 비교하기 때문에 도저히 만들 수 없는 수였다.

그래서 과감하게 완전탐색으로 갈아타기로 했다.

완전탐색에서는 최대 몇 까지 탐색하냐. 최몇탐이 중요한데.

이 문제에서 n과 비교할 수 있는 수는

최대 999999이다.

 

왜나면 n<=500000이고

버튼은 0~9까지 있으므로

최대 999999까지만 비교해보면 되는 것이다.

 

반복문으로 0~999999를 n과 비교해서 n과의 차이가 가장 작은 것 중에

작은값을 저장했다. 물론

비교할 수를 한자리씩 떼어서 고장난 버튼에 포함되어있는지 검사했다.

한자리씩 떼어서 비교하기 위해 나에겐 가장 편한 방법인 String과 charAt을 사용했다.

 

처음엔 while문으로 가장가까운 수를 찾아서 n까지 가기위해 ++ 또는 --를 하면서 카운트를 세었는데

그냥 가장가까운수 - n 의 절대값을 구하면 된다는 사실도 깨달았다.

그래서 가장가까운 수를 구한 다음

절대값(n-가장가까운수 ) + 가장가까운수의 자리값

을 해서 버튼을 누른 횟수를 구했다.

 

n이 전부 고장나지 않은 버튼인 경우엔 가장가까운 수에 n이 들어가게 되어서

n의 자리수만 더하면 되고

 

현재 채널인 100에서 그냥 +버튼이나 -버튼을 몇번 눌러서 가는 횟수가 빠른 경우가 있을 수 있기 때문에

따로 n-100의 절대값을 구해서 저장한다음

앞서말한 방법과 비교해서 더 낮은 수를 출력했다.

 

주석을 나름 자세히 작성해 놓았다.

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        String n = scan.next();
        int m = scan.nextInt();
        int [] a = new int[10]; //고장난 버튼을 표시할 배열
        
        for(int i=0; i<m; i++)  //고장난 버튼엔 -1을 넣는다.
            a[scan.nextInt()] = -1;
 
        if(n.equals("100")) 
            System.out.println(0);
        else {
            int min = Integer.MAX_VALUE;
            String v = "";//0 ~ 1000000까지의 숫자를 문자열화 하기위한~
            String closer = ""; //리모컨으로 입력할 수 있는 n과 가장 가까운 채널
            
            for(int i = 0; i<1000000; i++) {
                boolean isOk = true;
                v = i+""; //숫자를 문자열로 저장
                for(int j=0; j<v.length(); j++) { //고장난 버튼이 포함되어 있는지 검사
                    if(a[v.charAt(j)-'0'] == -1) { 
                        isOk = false;
                        break;
                    }
                }
                if(isOk) { //v에 고장난 버튼이 없으면 가장 가까운 채널을 찾는다. n-v로  + 또는 - 버튼을 몇번 눌러야하는지 계산
                    if(min > Math.abs(Integer.parseInt(n)-Integer.parseInt(v))) { 
                        min = Math.abs(Integer.parseInt(n)-Integer.parseInt(v));
                        closer = v; 
                    }
                }
            }
            
            int result1 = Math.abs(Integer.parseInt(n)-100); //result1에는 현재채널인 100에서 +와-만으로 n까지 갈때의 횟수를 저장
            if(closer.equals("")) //가장 가까운 수가 비어있으면 그냥 result1출력
                System.out.println(result1);
            else { //result2에는 n-closer로 closer에서 n까지 가기위한 횟수에 closer를 누르기위한 버튼 입력 횟수인 closer의 길이를 더한다.
                int result2 = Math.abs(Integer.parseInt(n)-Integer.parseInt(closer))+closer.length(); 
                if(result1>result2)
                    System.out.println(result2);
                else
                    System.out.println(result1);
            }
        }
    }