알고리즘34 :: BOJ_1107_리모컨

 

꽥님의 오픈프로필

이 문제에 접근 방법은 예외 상황을 잘 처리해야 합니다. 

주어진 수를 n 이라고 둔다면 Math.abs(100-goal) 과 최대범위(max) Math.abs(1000000-goal) 을 각각 계산해서 최솟값을 갱신해야 합니다. 왜 1000000 이냐면 범위값이 500000 라고 주어졌지만 사실은 1000000 에서 부터 조회할 경우 더 빠른 경우가 있기 때문입니다. 

저는 이 문제를 2가지 방법으로 구현해봤습니다. 

1) 내 마음대로

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
 
    private static int goal, n;
    private static int[] map;
    private static int ans = Integer.MAX_VALUE;
    private static void DFS(String str) {
        
        if(str.length()>6)
            return ;
        if(str.length()>=1) {
            int ss = Math.abs(goal-Integer.parseInt(str))+str.length();
            if(ans>ss) ans = ss;
            
            
        }
        
        
        
        boolean find = false;
        for(int i=0; i<=9; i++) {
            k:for(int j=0; j<n; j++) {
                if(i==map[j]) {
                    find = true;
                    break k;
                }
            }//end of for loop
            if(find == true) {
                find = false;
                continue;
            }
            DFS(str+i);
        }
        
        
    }
    public static void main(String[] args) throws Exception{
        // TODO Auto-generated method stub
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        goal = Integer.parseInt(br.readLine());
        n = Integer.parseInt(br.readLine());
        map = new int[n]; 
        
        if(n>0) {
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        for(int i=0; i<n; i++)
            map[i] = Integer.parseInt(st.nextToken());
        //end of for loop
        }
        int fir = Math.abs(goal - 100); //+ 만 누른 경우 
        if(ans>fir) ans = fir;
        int sec = Math.abs(1000000 - goal); //-만 누른 경우 
        if(ans>sec) ans = sec;
        
        DFS("");
        
        System.out.println(ans);
        
        
    }
 
}
 
 

 

2) 좀 더 효율적인 방법으로 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
 
public class Main {
 
    private static int goal, n;
    private static int[] map;
    private static int ans = 0;
    private static int f(int nn) {
        
        int len = 0;
        while(nn/10!=0) { //일의 자리란 소리임 
            int check = nn%10;
            nn/=10;
            for(int i=0; i<n; i++) {
                if(map[i] == check)
                    return -1;
            }
            len +=1;
        }
        for(int i=0; i<n; i++) {
            if(map[i] == nn%10) return -1;
        }
        len+=1;
        
        return len;
    
    }
    public static void main(String[] args) throws Exception {
        // TODO Auto-generated method stub
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        goal = Integer.parseInt(br.readLine());
        n = Integer.parseInt(br.readLine());
        
        map = new int[n];
        if(n>0) {
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=0; i<n; i++) {
            map[i] = Integer.parseInt(st.nextToken());
        }
        }
        ans = Math.abs(goal-100)>Math.abs(1000000-goal) ? Math.abs(1000000-goal) :Math.abs(goal-100);
        for(int i=0; i<=1000000; i++) {
            
            int    len = f(i);
                
            
            if(len != -1 && ans>Math.abs(goal-i)+len) {
                ans = Math.abs(goal-i)+len;
            }
            
        }
        System.out.println(ans);
    }
 
}