
https://www.acmicpc.net/problem/1107
문제분석
처음에는 사용 가능한 숫자를 가지고 모든 채널을 만들고, TreeSet을 활용해 N과 가장 가까운 정수를 찾아서 100과의 거리를 비교하면 되는 줄 알았다. 당연히 100과도 거리를 비교했다. 하지만 이 과정에서 자꾸 틀린 답이 나왔고, 이유를 보니 시간 초과가 메인일 것 같았다. 따라서 1~1_000_000 까지 모든 채널에 대하여"입력 가능 여부" 를 반환하도록 하였고, 브루트포스답게 딱 1M 개의 채널만 순회하니 정답을 찾을 수 있다.
코드
import java.io.*;
import java.util.*;
public class Main {
static Set<Integer> broken = new HashSet<>();
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
int M = Integer.parseInt(br.readLine());
if (M > 0) {
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i = 0; i < M; i++) broken.add(Integer.parseInt(st.nextToken()));
}
int ans = Math.abs(N - 100); // +/-만 쓰는 경우
// N 최대 500,000이라 보통 1,000,000까지 보면 충분합니다.
for (int ch = 0; ch <= 1_000_000; ch++) {
int len = typeLengthIfPossible(ch);
if (len >= 0) {
int press = len + Math.abs(ch - N);
ans = Math.min(press, ans);
}
}
System.out.println(ans);
}
// 입력 가능하면 "누른 숫자 버튼 개수" 반환, 불가능하면 -1
static int typeLengthIfPossible(int x) {
if (x == 0) {
return broken.contains(0) ? -1 : 1;
}
int len = 0;
while (x > 0) {
int d = x % 10;
if (broken.contains(d)) return -1;
len++;
x /= 10;
}
return len;
}
}

'알고리즘&PS > PS' 카테고리의 다른 글
| [JAVA] 백준 17298 오큰수 (0) | 2026.02.16 |
|---|---|
| [JAVA] 백준 1987 알파벳 (0) | 2026.02.16 |
| [JAVA] 백준 1038 감소하는 수 (0) | 2026.02.15 |
| [JAVA] 백준 1025 제곱수 찾기 (0) | 2026.02.14 |
| [JAVA] 백준 1022 소용돌이 예쁘게 출력하기 (0) | 2026.02.13 |