백준 1107번: 리모컨

문제

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

1107번: 리모컨

 

---

풀이

일부 숫자 버튼이 고장 나있고 +1 혹은 -1만큼 채널을 변경할 수 있는 +, - 버튼이 있는 리모컨과 무한대만큼의 채널이 있을 때 100번 채널부터 n번 채널로 가기 위해 버튼을 최소 몇 번을 눌러야 하는지를 구하는 문제입니다.

---

코드

C언어

버튼을 누르는 최솟값 min은 원하는 채널 번호(n)와 현재 채널 위치(100)와의 차이로 초기화합니다. 이 경우는 + 또는 - 버튼만 누르는 경우입니다.

그다음은 고장 나지 않은 숫자 버튼을 이용하여 가장 가까운 채널로 이동한 뒤에 + 또는 - 버튼을 누르는 경우입니다. 이때 채널은 무한대만큼 존재하지만 n의 범위는 500,000 이하입니다. n이 500,000일 때 0 또는 1,000,000부터 +, - 버튼만 누르는 횟수는 같기 때문에 i를 포함한 for문에서 999,999까지만 탐색합니다.

어떤 숫자를 숫자 버튼만 이용해서 이동할 때 고장 난 버튼이 없다면 몇 번 눌러야 하는지를 구하는 함수 length()가 있습니다. 이때 숫자가 0이라면 while문에 들어갈 수 없기 때문에 숫자 0 버튼의 고장 여부를 확인하고 0 또는 1을 반환합니다. length 함수 내부의 while문에선 숫자의 오른쪽부터 탐색하는데 해당 숫자 버튼이 고장 났다면 0을 반환합니다. while문이 끝나면 고장 난 버튼이 없다는 뜻으로 len을 반환합니다.

len = length(i)이라고 할 때 i로 이동할 수 있다면(len > 0) i로 숫자 버튼만으로 이동(len)하고 + 또는 - 버튼으로 이동(abs(n - i))하여 n까지 도달했을 때의 버튼을 누른 총 횟수(tmp)를 구하고 min과 비교합니다.

모든 비교가 끝나면 min값을 출력합니다.

#include <stdio.h>
#include <math.h>
#define math_min(a, b) a < b ? a : b
int broken[10] = { 0 };
int length(int i) {
	if (i == 0) {
		if (broken[0]) return 0;
		else return 1;
	}
	int len = 0;
	while (i) {
		if (broken[i % 10]) {
			return 0;
		}
		i /= 10;
		len++;
	}
	return len;
}
main() {
	int n, m, button;
	scanf("%d %d", &n, &m);
	while (m-- > 0) {
		scanf("%d", &button);
		broken[button] = 1;
	}
	int min = abs(n - 100);
	for (int i = 0; i < 1000000; i++) {
		int len = length(i);
		if (len > 0) {
			int tmp = len + abs(n - i);
			min = math_min(tmp, min);
		}
	}
	printf("%d", min);
}

자바

위의 C언어를 이용한 풀이와 방법은 동일하지만 length 함수를 따로 구현하지 않고 i를 포함한 for문 안에서 String str = String.valueOf(i)를 사용해서 i의 길이를 구한 뒤에 str의 길이까지 고장 난 버튼이 없는지 확인하는 방법을 사용했습니다.

import java.io.IOException;
import java.io.BufferedReader;
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));
        int n = Integer.parseInt(br.readLine());
        int m = Integer.parseInt(br.readLine());
        boolean[] broken = new boolean[10];
        if (m > 0) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            while (m-- > 0) {
                broken[Integer.parseInt(st.nextToken())] = true;
            }
        }
        int min = Math.abs(n - 100);
        if (n != 100) {
            for (int i = 0; i < 1000000; i++) {
                String str = String.valueOf(i);
                boolean isBroken = false;
                int len = str.length();
                for (int j = 0; j < len; j++) {
                    if (broken[str.charAt(j) - '0']) {
                        isBroken = true;
                        break;
                    }
                }
                if (!isBroken) {
                    int tmp = len + Math.abs(n - i);
                    min = Math.min(tmp, min);
                }
            }
        }
        System.out.println(min);
    }
}

 

---

결론

자바를 이용한 풀이가 C언어를 이용한 풀이보다 속도가 당연히 느릴 것이라는 것을 알 수 있었지만 더 깔끔하고 이해하기 쉬울 것 같다고 느꼈습니다. 앞으로 이런 자바의 장점을 잘 살릴 수 있는 코드를 짜고 싶다는 생각이 들었습니다.