HyeonSu

취미코딩 하는 개발자

[백준][1107번] 리모콘

Updated:

문제 URLPermalink

https://www.acmicpc.net/problem/1107 boj1107

나의 풀이Permalink

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int size = sc.nextInt();
            // 버튼이 고장나 있으면 true, 아니면 false
        boolean[] broken = new boolean[10];
        for (int i = 0; i < size; i++) {
            int c = sc.nextInt();
            broken[c] = true;
        }

        //ch100에서 바로 이동하는경우
        int ans = Math.abs(n - 100);

        for (int i = 0; i <= 1000000; i++) {
            // 길이 구하기
            int len = 1;
            if (i > 0) {
                len = (int) (Math.log10(i) + 1);
            }

            // 누를 수 없는 버튼이 포함되었는지 확인
            if (isPossible(i, broken))
                continue;

            // 답계산
            int cal = len + Math.abs(i - n);
            if (cal < ans) {
                ans = cal;
            }
        }
        System.out.println(ans);
    }

    static boolean isPossible(int ch, boolean[] broken){
        if(ch == 0)
            return broken[0];

        while(ch>0){
            if (broken[ch % 10]) {
                return true;
            }
            ch /= 10;
        }
        return false;
    }
}

느낀점Permalink

어느 숫자에 특정 숫자배열 요소들이 포함되어있나 검사하는 로직에서 복잡도를 높게 로직을 구현했다.

public static boolean isContain(int[] err, int ch) {
        while (ch > 0) {
            for (int er : err) {
                if (er == ch % 10) {
                    return true;
                }
            }
            ch /= 10;
        }
        return false;
    }

이런 방식보다 아래와 같이하면 o(n2)에서 o(n)으로 복잡도를 줄일 수 있다. boj1107-a

  • 런타임에러 해결법 m == 0인 경우에 readLine()을 불러서 문제가 되었다. 따라서 m==0인경우 호출 안하도록 설정했다. 
    String[] st = new String[0];
if(m>0) {
  st = bf.readLine().split(" ");
}

Leave a comment

You may also enjoy