[백준] no1107: 리모컨

문제

 

 

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

---

원리

1. 조건식

2. 브루트 포스 (레퍼런스)

---

풀이방법

1. 조건식

/**
 * 1. Integer 형 숫자키 배열은 0 1 2 3 4 5 6 7 8 9 10 11 까지
 * 2. 고장난 숫자키는 null 처리
 * 3. 만약 1이 null 되면 10과 11도 null
 * 4. 만약 0이 null 되면 10도 null
 *
 * 5. 비교는 총 3가지
 * 6. 주어진 채널의 맨 앞자리를 배열과 산술하여 절대값이 가장 작은 숫자키가 10이나 11일 경우,
 *    10이면 뒷자리도 전부 0으로 채운 숫자를 후보에 담음
 *    11이면 뒷자리도 전부 1으로 채운 숫자를 후보에 담음
 * 7. 10이나 11이 아니라면, 모든 자릿수를 배열과 비교하여 산술결과의 절대값이 제일 작은 수로 모아서 후보에 담음
 * 8. 남은 숫자키 중 제일 큰 수로 채널길이-1 사이즈의 채널을 채워 만들고, (목표 채널-만든채널)의 결과와 (후보채널-목표채널)의 절대값을 비교
 * 9. 더 작은 수의 결과를 갖는 채널을 최종 결과로 출력
 * 10. 엣지 케이스 : 만약 목표 채널이 100일 경우 -> 100에서 시작이므로 0을 반환
 */

2. 브루트 포스 : 아래 레퍼런스 참고

---

나의 코드

1. 조건문 + 반복문 [실패]

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;
import java.util.stream.IntStream;

public class no1107 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String strN = br.readLine();
        int[] strArr = Arrays.stream(strN.split("")).mapToInt(a->Integer.parseInt(a)).toArray();
        int N = Integer.parseInt(strN);
        int T = Integer.parseInt(br.readLine());
        StringTokenizer st = T==0? null : new StringTokenizer(br.readLine(), " ");
        int result = strN.length();

        if(st==null) {
            System.out.println(result);
        } else if(N==100) {
            System.out.println(0);
        } else {
            result += calculate(T, st, strN, N, strArr, result);
            System.out.println(result);
        }
    }

    private static int calculate (int T, StringTokenizer st, String strN, int N, int[] strArr, int result) {
        Integer[] arr = new Integer[10];
        for (int i = 0; i < 10; i++) arr[i] = i;
        for (int i = 0; i < T; i++) arr[Integer.parseInt(st.nextToken())] = null;

        int[] resultArr = new int[strN.length()];
        for (int i = 0; i < strN.length() ; i++) {
            for(int j=0; j < arr.length; j++) {
                if(arr[j]==null) continue;
                if(Math.abs(strArr[i]-resultArr[i])>Math.abs(strArr[i]-arr[j])) resultArr[i] = arr[j];
            }
        }
        String close = "";
        for(int i=0; i<resultArr.length;i++) close += resultArr[i];
        int closeInt = Integer.parseInt(close);

        result += Math.abs(closeInt - N);

        return result;
    }
}

 

2. 조건을 세분화 한 반복문 [로컬 테스트 성공  => 백준에서 NumberFormatRuntime에러]

: 최대 500000까지의 범위이고, 로컬에서도 500000이상의 연산도 잘 되나, 백준에서 에러 발생

import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;

public class no1107 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String strN = br.readLine(); // 목표 채널의 String 형태. 숫자 비교와 길이를 구하기 위함
        int[] arrN = Arrays.stream(strN.split("")).mapToInt(a-> Integer.parseInt(a)).toArray(); // 채널의 각 숫자를 나눈 숫자형 배열로 변환
        Integer N = Integer.parseInt(strN); // 목표 채널의 숫자형
        int result = 0;

        List<Integer> buttons = new ArrayList<>(12);  // 리모콘 숫자키
        for (int i = 0; i < 12; i++) buttons.add(i, i);
        int T = Integer.parseInt(br.readLine());
        if (T!=0) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");

            brokenButtons(T, st, buttons); // 고장난 버튼을 제외시킴

            Integer candidate = checkHead(buttons, arrN); //앞자리가 10 이나 11일 경우. 아닐경우 0으로 반환

            if (candidate == 0) candidate = mathAbs(buttons, arrN);
            String str = "";
            for (int i = buttons.size() - 3; i >= 0; i--) {
                if (buttons.get(i) != null) {
                    int temp = arrN.length;
                    while (temp-- > 0) str += buttons.get(i);
                    break;
                }
            }
            Integer secondCandidate = Integer.valueOf(str);

            if (Math.abs(secondCandidate - N) > Math.abs(candidate - N)) {
                result = Math.abs(candidate - N) + arrN.length;
            } else {
                result = Math.abs(secondCandidate - N) + arrN.length;
            }
        }

        result = N ==100 ? 0 : result;

        System.out.println(result);
    }

    private static void brokenButtons (int T, StringTokenizer st, List<Integer> buttons) {
        for (int i = 0; i <T ; i++) {
            Integer broken = Integer.parseInt(st.nextToken());
            if (buttons.contains(broken)) {
                if(broken.equals(0)) {
                    buttons.set(0, null); buttons.set(10, null);
                } else if (broken.equals(1)) {
                    buttons.set(1, null); buttons.set(10, null); buttons.set(11, null);
                } else {
                    buttons.set(broken, null);
                }
            }
        }
    }


    /**
     * * 6. 주어진 채널의 맨 앞자리를 배열과 산술하여 절대값이 가장 작은 숫자키가 10이나 11일 경우,
     *     *    10이면 뒷자리도 전부 0으로 채운 숫자를 후보에 담음
     *     *    11이면 뒷자리도 전부 1으로 채운 숫자를 후보에 담음
     * @param buttons
     * @param arrN
     * @return
     */
    private static Integer checkHead (List<Integer> buttons, int[] arrN) {
        Integer candidate = 0;
        Integer min = 0;
        Integer minGap = 10;
        int head = arrN[0];
        for(int i = 0 ; i <buttons.size() ; i++) {
             if (buttons.get(i)!=null && minGap>Math.abs(head - buttons.get(i))) {
                 minGap = Math.abs(head - buttons.get(i));
                 min = buttons.get(i);
             }
        }
        if (min.equals(10)) {
            String str = "10";
            for(int i = 1 ; i <arrN.length-1 ; i++) str += 0;
            candidate = Integer.valueOf(str);
        } else if (min.equals(11)) {
            String str = "11";
            for(int i = 1 ; i <arrN.length-1 ; i++) str += 1;
            candidate = Integer.valueOf(str);
        }

        return candidate;
    }


    /**
     * 7. 10이나 11이 아니라면, 모든 자릿수를 배열과 비교하여 산술결과의 절대값이 제일 작은 수로 모아서 후보에 담음
     * 8. 남은 숫자키 중 제일 큰 수로 채널길이-1 사이즈의 채널을 채워 만들고, (목표 채널-만든채널)의 결과와 (후보채널-목표채널)의 절대값을 비교
     * 9. 더 작은 수의 결과를 갖는 채널을 최종 결과로 출력
     */
    private static Integer mathAbs(List<Integer> buttons, int[] arrN) {
        String str = "";
        for(int i = 0; i <arrN.length; i++) {
            Integer min = 0;
            Integer minGap = 10;
            if(i==0||buttons.get(0)!=null) {
                for(int j = 1; j < buttons.size(); j++) {
                    Integer head = arrN[i];
                    Integer button = buttons.get(j);
                    if (button!= null && Math.abs(head-button)<minGap) {
                        minGap = Math.abs(head-button);
                        min = button;
                    }
                }
            }

            for(int j = 0; j <buttons.size(); j++) {
                Integer head = arrN[i];
                Integer button = buttons.get(j);
                if (button!= null && Math.abs(head-button)<minGap) {
                    minGap = Math.abs(head-button);
                    min = button;
                }
            }
            str += min;
        }

        return Integer.valueOf(str);
    }
}

---

레퍼런스 코드

브루트 포스 : 최대 채널을 고정해놓고 완전탐색하는 방식

참고 링크 : https://moonsbeen.tistory.com/64

import java.util.*;
 
public class Main {    
    
    public static void main(String[] args)  {
        Scanner scan = new Scanner(System.in);
        
        int target = scan.nextInt();
        int m = scan.nextInt();
        
        boolean[] broken = new boolean[10];
        for(int i = 0; i < m; i++) {
            int n = scan.nextInt();
            broken[n] = true;
        }
        
        int result = Math.abs(target - 100); //초기값 설정
        for(int i = 0; i <= 999999; i++) {
            String str = String.valueOf(i);
            int len = str.length();
            
            boolean isBreak = false;
            for(int j = 0; j < len; j++) {
                if(broken[str.charAt(j) - '0']) { //고장난 버튼을 눌러야 하면
                    isBreak = true; 
                    break; //더 이상 탐색하지 않고 빠져나온다.
                }
            }
            if(!isBreak) { //i를 누를때 고장난 버튼을 누르지 않는다면
                int min = Math.abs(target - i) + len; //i를 누른 후(len) target까지 이동하는 횟수(target - i)
                result = Math.min(min, result);
            }
        }        
        System.out.println(result);
    }
}