[BOJ] 1107번 리모컨

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

1107번: 리모컨

 

N의 범위가 500,000이다. 

Brute Force로 했을 때, 백만개의 데이터에 대해 for문을 돌려야 하므로 당연히 시간초과가 나겠거니 하고, 중복조합 등 다양한 방법으로 접근했지만, 생각보다 너무 복잡해져서, 구글링을 해보았다.

그런데 백만개의 데이터를 일일히 해도 시간초과가 나지 않는 것 같아 실제로 해보니 통과했다. 

 

제한시간 2초에, 연산은 백만번에 O(N)이면 괜찮나 보다.

 

import sys
input = sys.stdin.readline

def check(n):
    n = str(n)
    for i in n:
        if i in arr:
            return False
    return True

now = 100
target = int(input())
k = int(input())
if k!=0:
    arr = list(input().rstrip().split())

    answer = abs(100-target)
    for i in range(1000001):
        if check(i):
            answer = min(answer, len(str(i)) + abs(i-target))

    print(answer)
    
else:
    print(min(abs(100-target), len(str(target))))