공부 149일차: 백준 1107번 리모컨 자바 java

1107 리모컨

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

1107번: 리모컨

 

 

 

 

---

백준 1107번 문제 리모컨

---

문제

---

 

 

 

 

---

과정 생각해보기 & 오답

---

 

바로 오답부터..

import java.io.*;
import java.util.*;
 
public class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        
        int n = Integer.parseInt(br.readLine());    // 채널
        
        
        int m = Integer.parseInt(br.readLine());    // 고장난 버튼 개수
        int[] brokenBtn = new int[m];    // 고장난 버튼 목록
        
        int[] originalBtn = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
        ArrayList<String> btns = new ArrayList<String>();
        int count = 0;    // 버튼 누른 횟수
        int currentCh = 100;    // 현재 채널
        
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < m; i++) {
            brokenBtn[i] = Integer.parseInt(st.nextToken());
        }
 
        if(n == 100) {    // 원하는 채널이 100이면 움직일 필요 없으므로
            System.out.println(0);    // 0을 출력한 뒤
            return;                    // 코드를 끝낸다
        }
        
        for(int i = 0; i < 10; i++) {            
            // 오름차순으로 입력되는 게 아니므로 망가진 버튼 다 검사해야 함
            for(int num : brokenBtn) {
                if(originalBtn[i] == num) {
                    originalBtn[i] = -1;    // 고장났으면 -1로 초기화
                }
            }
            
            if(originalBtn[i] != -1) {
                btns.add(originalBtn[i]+"");    // list에 넣기
            }
        }
        
        /*디버깅
        System.out.println(Arrays.toString(originalBtn));
        for(String str : btns) {
            System.out.print(str+" ");
        }
        */
        
        /*
        구할 수 있는 숫자 조합 다 만들기 -> min = Math.min(min, n - 숫자조합 + 숫자의 자리수)
         */
    }
}
 

 

이렇게 접근했는데 숫자 조합 만드는 데서 막혔다

배열에 주어진 숫자들로 만드려고 한다면 할 수는 있겠지만 너무 복잡하다는 생각..

 

그리고 방법을 찾았다

1부터 999,999까지 (n이 500,000이고, 금지된 숫자가 많을 때 999,999가 가장 가까울 수 있기 때문) 탐색하고, 

금지된 버튼이 들어가 있다면 탐색에서 제외한다

 

어떻게 조합할지를 고민하는 게 아니라, 다 구하고 거기서 제외시키는 것!

 

완전 브루트 포스 문제

 

참고 블로그

https://moonsbeen.tistory.com/64

https://nanyoungkim.tistory.com/124

https://1-7171771.tistory.com/37

 

 

 

---

정답 인정 코드

---

 

import java.io.*;
import java.util.*;
 
public class Main {
    public static void main(String[] args) throws IOException{
        //BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //StringTokenizer st = null;
        Scanner sc = new Scanner(System.in);
        ArrayList<Integer> brokenBtn = new ArrayList<Integer>();
        
        int n = sc.nextInt();    // 채널
        int m = sc.nextInt();    // 고장난 버튼 개수
        
        //st = new StringTokenizer(br.readLine());
        for(int i = 0; i < m; i++) {
            brokenBtn.add(sc.nextInt());
        }
        
        int min = Math.abs(n - 100); // 모든 숫자버튼이 고장났을 때는 +, -로만 움직여야 한다
        for(int i = 0; i <1_000_000; i++) {
            String str = String.valueOf(i);
            int len = str.length();
            
            boolean isBreak = false;
            for(int j = 0; j < len; j++) {
                if(brokenBtn.contains(str.charAt(j)-'0')) {    
                    // 0~999,999에 해당하는 숫자 i의 자리수 중 하나가 고장난 버튼의 숫자라면
                    isBreak = true;
                    break;    // 빠져나온다 (그 숫자 거름)
                }
            }
            
            if(!isBreak) {
                min = Math.min(min ,Math.abs(n - i)+len);
            }
        }
 
        System.out.println(min);
    }
}
 

 

다 똑같이해도 BufferedReader로 입력하면 NullPointer 런타임에러가 뜨는데 이유가 짐작가지 않는다

 

 

 

---

또 숫자 문제를 문자열로 바꿔서 더하려다가.............

직접 구하는 게 아니라 뺴는 여집합 같은 접근법도 있음을 다시 한 번 상기하기