곽로그

[백준 1107, Java] 리모컨 본문

알고리즘/백준

[백준 1107, Java] 리모컨

일도이동 2020. 11. 27. 00:36
반응형

문제

www.acmicpc.net/problem/1107

 

1107번: 리모컨

첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다.  둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼

www.acmicpc.net

 

주의!

첫번째도 그렇고 두번째도 0때문에 틀렸다. 처음엔 number==0인 경우를 생각하지 않아서 틀렸다. number의 범위에서 가능한 모든 경우를 따지는 습관을 들이자. 위의 경우 number가 음이아닌 정수이므로 >0 뿐만아니라 0인 경우도 고려해줘야한다. 

 

반례

0

10

0 1 2 3 4 5 6 7 8 9

    public static boolean isValid(int number){
        if(number==0){
            return !isBroken[0];
        }
        while(number>0){
            int n = number%10;
            if(isBroken[n]){
                return false;
            }
            number/=10;
        }
        return true;
    }

 

 

 

코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    public static int CURRENT_POINT = 100;
    public static  int DESTINATION;
    public static int MIN_CLICK = 500000;
    public static int N;
    public static int[] brokenButtons;

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

        DESTINATION = Integer.parseInt(br.readLine());
        N = Integer.parseInt(br.readLine());
        
        if(N>0){
            brokenButtons = new int[N];
            st = new StringTokenizer(br.readLine());
            for(int index = 0 ; index<N; index++){
                brokenButtons[index] = Integer.parseInt(st.nextToken());
            }
        }
        else {
            brokenButtons  = new int[10];
            Arrays.fill(brokenButtons, -1);
        }
        

        findMinClick();
        bw.write(String.valueOf(MIN_CLICK));
        bw.flush();

        br.close();
        bw.close();


    }
    public static void findMinClick(){
        if(CURRENT_POINT== DESTINATION){
            MIN_CLICK = 0;
        }
        else if(CURRENT_POINT< DESTINATION){
            // 현재위치에서 +만 이용해서 목적지로 이동
            MIN_CLICK = Math.min(MIN_CLICK, DESTINATION-CURRENT_POINT);

            //목적지에서 목적지보다 작은 위치 중에서 가장 가까운 위치찾기
            int tempPoint = DESTINATION;
            while(tempPoint>CURRENT_POINT){
                if(!isBroken(tempPoint)){
                    int numberCount = getCount(tempPoint);
                    int plusMinus = DESTINATION - tempPoint;
                    MIN_CLICK = Math.min(MIN_CLICK, numberCount+plusMinus);
                    break;
                }
                --tempPoint;
            }

            // 목적지에서 목적기보다 큰 위치 중에서 가장 가까운 위치 찾기
            tempPoint = DESTINATION;
            int upperBound = DESTINATION + MIN_CLICK;
            while(tempPoint<upperBound){
                if(!isBroken(tempPoint)){
                    int numberCount = getCount(tempPoint);
                    int plusMinus = tempPoint- DESTINATION;
                    MIN_CLICK = Math.min(MIN_CLICK, numberCount+plusMinus);
                    break;
                }
                ++tempPoint;
            }
        }
        else{
            //현재 위치에서 -만 이용해서 목적지로 이동
            MIN_CLICK = Math.min(MIN_CLICK, CURRENT_POINT-DESTINATION);

            //목적지에서 목적지보다 작은 위치 중에서 가장 가까운 위치찾기
            int tempPoint = DESTINATION;
            while(tempPoint>=0){
                if(!isBroken(tempPoint)){
                    int numberCount = getCount(tempPoint);
                    int plusMinus = DESTINATION - tempPoint;
                    MIN_CLICK = Math.min(MIN_CLICK, numberCount+plusMinus);
                    break;
                }
                --tempPoint;
            }

            // 목적지에서 목적기보다 큰 위치 중에서 가장 가까운 위치 찾기
            tempPoint = DESTINATION;
            int upperBound = DESTINATION + MIN_CLICK;
            while(tempPoint<upperBound){
                if(!isBroken(tempPoint)){
                    int numberCount = getCount(tempPoint);
                    int plusMinus = tempPoint- DESTINATION;
                    MIN_CLICK = Math.min(MIN_CLICK, numberCount+plusMinus);
                    break;
                }
                ++tempPoint;
            }
        }
    }

    public static boolean isBroken(int point){
        int temp = point;
        boolean isBroken = false;

        if(point==0){
            for(int index = 0 ; index< brokenButtons.length;index++){
                if(brokenButtons[index] == 0){
                    isBroken = true;
                }
            }
        }
        else{
            while(temp>0){
                int remainder = temp%10;
                for(int index = 0 ; index<brokenButtons.length; index++){
                    if(brokenButtons[index] == remainder){
                        isBroken = true;
                    }
                }
                temp /=10;
            }

        }

        return isBroken;
    }

    public static int getCount(int  num){
        int count = 0;

        if(num ==0){
            count =1;
        }
        else{
            while(num>0){
                num /=10;
                ++count;
            }
        }


        return count;
    }
}

 

 

2021.01.14수정

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {
    public static int N;
    public static int M;
    public static boolean[] isBroken;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());
        M = Integer.parseInt(br.readLine());

        isBroken = new boolean[10];
        if(M!=0){
            st =new StringTokenizer(br.readLine()," ");
            for(int i = 0; i<M; i++){
                isBroken[Integer.parseInt(st.nextToken())] = true;
            }
        }

        int minPush = Math.abs(N-100);

        //N보다 큰 숫자를 누른다
        int biggerNumber = N;
        while(biggerNumber<=N+minPush){
            if(isValid(biggerNumber)){
                int pushCount = numberCount(biggerNumber);
                pushCount+=Math.abs(biggerNumber-N);
                minPush=Math.min(minPush,pushCount);
            }
            biggerNumber++;
        }

        //N보다 작은 숫자를 누른다
        int smallerNumber = N-1;
        while(smallerNumber>=0){
            if(isValid(smallerNumber)){
                int pushCount = numberCount(smallerNumber);
                pushCount+=Math.abs(smallerNumber-N);
                minPush=Math.min(minPush,pushCount);
            }
            smallerNumber--;
        }

        bw.write(String.valueOf(minPush));
        bw.flush();

    }
    public static boolean isValid(int number){
        if(number==0){
            return !isBroken[0];
        }
        while(number>0){
            int n = number%10;
            if(isBroken[n]){
                return false;
            }
            number/=10;
        }
        return true;
    }

    public static int numberCount(int number){
        if(number==0){
            return 1;
        }
        int count = 0;
        while(number>0){
            ++count;
            number/=10;
        }
        return count;
    }
}
반응형
저작자표시 비영리 변경금지

'알고리즘 > 백준' 카테고리의 다른 글

[백준 3085, Java] 사탕 게임  (0) 2020.11.27
[백준 1476, Java] 날짜 계산  (0) 2020.11.27
[백준 9461, Java] 파도반 수열  (0) 2020.11.27
[백준14500, Java] 테트로미노  (0) 2020.11.26
[백준 2800, Java] 괄호제거  (1) 2020.11.26
'알고리즘/백준' Related Articles more
Comments