리모컨(1107)

리모컨(1107)

import java.io.*;
import java.util.*;

public class Main{
    
  static boolean[] rc = new boolean[10];
  
  public static void main(String[] args) throws IOException{
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    StringBuilder sb = new StringBuilder();
    
    int n = Integer.parseInt(br.readLine()), m = Integer.parseInt(br.readLine());
    
    //고장난 버튼
    if(m != 0){
      StringTokenizer st = new StringTokenizer(br.readLine());
      while(st.hasMoreTokens()){
        int tmpN = Integer.parseInt(st.nextToken());
        rc[tmpN] = true;
      }
    }
    
    int cnt = pushCount(n);
    
    sb.append(cnt);
    
    bw.write(sb.toString());
    bw.flush();
    bw.close();
    br.close();
  }
  
  public static int pushCount(int n){
    
    // 원하는 채널이 100이면  현재위치
    if(n == 100) return 0;
    
    // 원하는 채널을 +-로만 이동
    int cnt = Math.abs(n - 100);
    
    for(int i = 0; i < 1000000; i++){
      // 입력한 숫자 0부터 999999까지
      String pushNum = String.valueOf(i);
      
      boolean flag = true;
      
      // 입력한 숫자에 고장난 버튼의 숫자가 있는지
      for(int j = 0; j < 10; j++){
        // 고장난 버튼
        if(rc[j]){
          // 고장난 버튼이 입력한 숫자에 포함된 숫자라면
          if(pushNum.indexOf(String.valueOf(j)) != -1){
            flag = false;
            break;
          }
        }
      }
      
      if(flag){
        cnt = Math.min(cnt, Math.abs(n - i) + pushNum.length());
      }
    }
    
    return cnt;
  }
}

풀이과정

1. 처음에는 주어진 숫자에서 앞에 하나씩 수를 분리하여 사용 혹은 근사치를 찾는 알고리즘을 구현하였다.
2. 예시들은 맞았지만 정답 제출을 하니 틀렸다고 나왔다.
3. 반례를 찾아보니 99999 / 2 / 8 9 가 입력이 되었을 때 정답처리가 틀렸다.
4. 이유는 위의 경우 100000를 입력하고 - 버튼을 눌러 7이 정답인데, 내가 구현한 것을 보면 앞자리 9를 비교하여 근사치인 7을 입력하기 때문에 정답이 높게나오게 되었다.
5. 그래서 다른 사람들의 풀이를 참고해 보니 완전탐색을 이용하여 풀어야 한다고 하여, 다시 구현하였다.
6. int형으로 비교하기에는 로직이 복잡해질 것 같아 String 형으로 변환하여, 고장난 버튼의 포함여부를 비교하는 식으로 하여 로직을 구현하였다.

- 성공
- 메모리 : 127608 KB
- 시간 : 384 ms

보안점

1. 주어진 부분만을 고민을 하여 로직을 짰다.
2. 좀 더 경우의 수를 생각할 수 있게 생각의 폭을 넓혀야 한다는 것을 다시 깨달았다.