[BOJ/JAVA] 백준 1107번 : 리모콘 (다른 사람 코드 공부해보자)

1107번: 리모컨

 

 

---

 

• 생각

 

문제는 리모컨을 눌러서 채널 N을 트는 것이다.

 

조건)

1. 처음 시작은 100번이다.

2. 고장난 번호가 있다.

3. 번호를 누르는 것 외로 +,-를 사용할 수 있다.

 

풀이)

1. 처음 시작 채널 100에서 채널 N을 +,-로만 틀 떄의 누르는 횟수를 answer에 저장한다.(Math.abs를 사용하면 편리)

2. 고장난 번호는 boolean 배열을 이용해서 해당 index에 true로 설정해놓는다. (배열의 false index는 사용가능)

3. dfs를 돌린다.

4. basecase는 현재 채널이 채널 N의 길이보다 길어지면 그만 돌린다. (채널 N의 길이보다 +1 을 해줘야한다.)

 **현재 길이보다 +1 해준 이유는 값이 9999이런식으로 가는데 9를 쓰지 못하는 경우 +1을 해주지않으면 8888에서         +로 9999를 만들어야 하는데, +1해주면 10000에서 -한번만 누르면 가능함.

5. basecase에 걸리지 않으면 현재 채널까지 누른 횟수에서 +,-를 사용해서 채널 N을 만들 때의 누른 횟수를 answer로 초기화 시킨다.

6. 반복문으로 채널 0~9번을 누르면서 dfs를 돌린다. (고장난 버튼은 누르지 않음)

 

 

 

• 코드

 

import java.io.IOException;
import java.io.InputStream;
import java.util.InputMismatchException;

public class Main {
	static int N, answer, limit;
	static boolean[] array;

	public static void main(String[] args) throws Exception {
		SetData();
		System.out.println(answer);
	}

	// 데이터
	private static void SetData() throws Exception {
		InputReader in = new InputReader(System.in);

		N = in.nextInt();
		array = new boolean[10];
		// 현재 길이보다 +1 해준 이유는 값이 9999이런식으로 가는데 9를 쓰지 못하는 경우 +1을 해주지않으면 8888에서 +로 9999를 만들어야 하는데
		// +1해주면 10000에서 -한번만 누르면 가능함.
		limit = (N+"").length() + 1;

		int numberOfBrokenRemoteControl = in.nextInt();
		for (int i = 0; i < numberOfBrokenRemoteControl; i++)
			array[in.nextInt()] = true;

		// 초기값 100에서 +,-만 사용해서채널 N을 틀 때 누르는 수
		answer = Math.abs(N - 100);
		
		for (int i = 0; i < 10; i++) {
			if (array[i])
				continue;
			
			dfs(i, 1);
		}
	}

	private static void dfs(int value, int count) {
		// basecase (현재 수가 N보다 높아지면 그만 돌린다.)
		if (limit < count)
			return;

		// 현재 누른 횟수와 +,-만 사용해서 채널 N을 틀 때 누르는 수
		answer = Math.min(answer, count + Math.abs(N - value));
		for (int i = 0; i < 10; i++) {
			if (array[i])
				continue;
			
			dfs((value * 10) + i, count + 1);
		}
	}
}

class InputReader {
	private final InputStream stream;
	private final byte[] buf = new byte[8192];
	private int curChar, snumChars;

	public InputReader(InputStream st) {
		this.stream = st;
	}

	public int read() {
		if (snumChars == -1)
			throw new InputMismatchException();
		if (curChar >= snumChars) {
			curChar = 0;
			try {
				snumChars = stream.read(buf);
			} catch (IOException e) {
				throw new InputMismatchException();
			}
			if (snumChars <= 0)
				return -1;
		}
		return buf[curChar++];
	}

	public int nextInt() {
		int c = read();
		while (isSpaceChar(c)) {
			c = read();
		}
		int sgn = 1;
		if (c == '-') {
			sgn = -1;
			c = read();
		}
		int res = 0;
		do {
			res *= 10;
			res += c - '0';
			c = read();
		} while (!isSpaceChar(c));
		return res * sgn;
	}

	public long nextLong() {
		int c = read();
		while (isSpaceChar(c)) {
			c = read();
		}
		int sgn = 1;
		if (c == '-') {
			sgn = -1;
			c = read();
		}
		long res = 0;
		do {
			res *= 10;
			res += c - '0';
			c = read();
		} while (!isSpaceChar(c));
		return res * sgn;
	}

	public int[] nextIntArray(int n) {
		int a[] = new int[n];
		for (int i = 0; i < n; i++) {
			a[i] = nextInt();
		}
		return a;
	}

	public String nextLine() {
		int c = read();
		while (isSpaceChar(c))
			c = read();
		StringBuilder res = new StringBuilder();
		do {
			res.appendCodePoint(c);
			c = read();
		} while (!isEndOfLine(c));
		return res.toString();
	}

	public boolean isSpaceChar(int c) {
		return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
	}

	private boolean isEndOfLine(int c) {
		return c == '\n' || c == '\r' || c == -1;
	}
}

 

 

 

• 다른 사람 코드

가져온 이유) 내 코드보다 시간이 5배 정도 빠르다. 공부해볼 필요가 있다.

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;
    }
    
}