[백준] 1107 : 리모컨

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

1107번: 리모컨

+,- 버튼만 사용해서 도달하는 경우와 버튼으로 바로 채널로 이동하여 +,- 버튼 사용하는 경우 두 가지 중 최솟값을 구하려고 했다.

가장 차이가 적은 고장난버튼이 포함되어있지 않은 채널을 구하는 방법을 고민하다가,

모든 경우의 수를 전부 탐색할 때, 입력된 수부터 탐색하여 해당 수에 고장난버튼이 있으면 ++해서 탐색, --해서 탐색

두 가지를 돌렸다. 그런데 구현을 너무 복잡하게 했는지 계속 오류가 떠서 그냥 포기하고 다른 분의 코드 확인함.

논리는 똑같았으나 굉장히 간결하게 정리된 코드였다.

**M==0인 경우를 생각못해서 실패뜸. 항상 범위는 신경쓰고 코드를 짜자

실패했던 코드구현도 성공하면 업로드하기.

 

메모리 : 64692 KB

시간 : 332 ms

코드길이 : 1118 B

 

[내코드]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st;
		
		int N = Integer.parseInt(br.readLine());
		int M = Integer.parseInt(br.readLine());
		
		//고장난 버튼을 탐색없이 바로 알 수 있게 boolean타입 배열로 선언해줌
		boolean[] brokenButton = new boolean[10];
		if(M != 0) {
			st = new StringTokenizer(br.readLine());
			for(int m = 0; m < M; m++) {
				int bntNum = Integer.parseInt(st.nextToken());
				//입력된 고장난 버튼값의 위치를 true로 변환
				brokenButton[bntNum] = true;
			}
		}
		
		//+,-로만 움직이는 경우를 초깃값으로 설정
		//N이 100보다 작을 수 있기 때문에 절댓값으로 해줌
		int result = Math.abs(N - 100);
		
		//버튼이 하나밖에 안남았을 경우 가장 최소로 접근할 수 있는 최댓값은 같은 10만대이므로 10만대의 최댓값인 999999
		for(int i = 0; i <= 999999; i++) {
			//숫자를 하나씩 가져와야 하기 때문에 String으로 변환시켜줌
			//toString은 NPE 발생가능성이 있어서 valueOf로 사용
			String str = String.valueOf(i);
			//해당 str의 길이만큼 for문을 돌아줘야 함
			int len = str.length();
			
			//고장난 버튼이 있는지 확인하는 boolean변수
			boolean isBroken = false;
			for(int j = 0; j < len; j++) {
				//char값으로 가져와지기 때문에 '0'을 빼줘야 원하는 int값이 나온다
				//ex ) '0'은 48, '1'은 49
				//고장난버튼은 true
				if(brokenButton[str.charAt(j) - '0']) {
					//true로 변환시켜서 고장난 버튼이 존재함을 알려줌
					isBroken = true;
					break;
				}
			}
			//for문을 다 돌았는데도 isBroken이 false면 if문 진입
			if(!isBroken) {
				//i가 N보다 작을 수 있으므로 절댓값으로 만들어줌
				//+,-로 이동하는 수 + 버튼을 눌러야 하는 횟수 = i의 길이
				int min = Math.abs(N - i) + len;
				//+,-로만 이동하는 경우랑 비교해서 더 작은수가 최솟값.
				result = Math.min(min, result);
			}
		}
		sb.append(result);
		System.out.print(sb);

	}

}

 

1등코드

메모리 : 12936 KB

시간 : 72 ms

코드길이 : 3990 B

 

[상위권 코드]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int m = Integer.parseInt(br.readLine());
        int ret = (n > 100)? n - 100 : 100 - n;
        boolean[] isBrokenButton;
        StringTokenizer st;
        
        if(m == 0) {
            System.out.print((String.valueOf(n).length() < ret)? String.valueOf(n).length() : ret);
            return;
        }
        
        st = new StringTokenizer(br.readLine());
        isBrokenButton = new boolean[10];
        
        if(n == 100) {
            System.out.print(0);
            return;
        } else if(m == 10) {
            System.out.print(ret);
            return;
        }
        
        while(st.hasMoreTokens())
            isBrokenButton[Integer.parseInt(st.nextToken())] = true;

        System.out.print(getPushCountOfButtonsToMoveChannel(n, isBrokenButton));
    }
    
    private static int getPushCountOfButtonsToMoveChannel(int destChannel, boolean[] isBrokenButton) {
        int ret = (destChannel > 100)? destChannel - 100 : 100 - destChannel;
        int lowChannel = -1, highChannel = -1, maxChannel = 100;
        int divider = (destChannel > 0)? ((int) Math.pow(10, (int) Math.log10(destChannel))) : 1;
        boolean isBrokenDestChannel = false;

        for(int i = divider; i > 0; i /= 10) {
            if(isBrokenButton[destChannel / i % 10]) {
                isBrokenDestChannel = true;
                break;
            }
        }
        
        if(!isBrokenDestChannel) {
            int retOfDestChannel = String.valueOf(destChannel).length();
            return (retOfDestChannel < ret)? retOfDestChannel : ret;
        }
        
        for(int i = 0; i < (int) Math.log10(destChannel); i++)
            maxChannel *= 10;
        
        for(int i = destChannel - 1; i >= 0; i--) {
            boolean isBrokenLowChannel = false;
            int brokenDivider = 0;
            
            divider = (i > 0)? ((int) Math.pow(10, (int) Math.log10(i))) : 1;
            
            for(int j = divider; j > 0; j /= 10) {
                if(isBrokenButton[i / j % 10]) {
                    isBrokenLowChannel = true;
                    brokenDivider = j;
                    break;
                }
            }

            if(isBrokenLowChannel) {
                i -= i % brokenDivider;
            } else {
                lowChannel = i;
                break;
            }
        }

        for(int i = destChannel + 1; i < maxChannel; i++) {
            boolean isBrokenHighChannel = false;
            int brokenDivider = 0;
            
            divider = (i > 0)? ((int) Math.pow(10, (int) Math.log10(i))) : 1;
            
            for(int j = divider; j > 0; j /= 10) {
                if(isBrokenButton[i / j % 10]) {
                    isBrokenHighChannel = true;
                    brokenDivider = j;
                    break;
                }
            }

            if(isBrokenHighChannel) {
                i -= i % brokenDivider;
                i += brokenDivider - 1;
            } else {
                highChannel = i;
                break;
            }
        }
        
        if(lowChannel > -1) {
            int retOfLowChannel = String.valueOf(lowChannel).length();
            
            retOfLowChannel += destChannel - lowChannel;
            ret = (retOfLowChannel < ret)? retOfLowChannel : ret;
        }

        if(highChannel > -1) {
            int retOfHighChannel = String.valueOf(highChannel).length();
            
            retOfHighChannel += highChannel - destChannel;
            ret = (retOfHighChannel < ret)? retOfHighChannel : ret;
        }
        
        return ret;
    }
    
}