permus = list(permus) -> 제너레이터를 list로 변환하면 모두 메모리에 올라가서 메모리 초과남 주의!! list 변환 없이 제너레이터 그대로 순회하면 됨!elem_cnt = abs(N - num) + i -> 두 수의 차이(+ or - 눌러야 하는 횟수) 계산 후 꼭 i 더하기! (해당 숫자를 만들기 위해 i번 버튼을 누르는 것이므로)
# 현재 채널 100번 -> N번으로 이동하기 위해 버튼을 최소 몇 번 눌러야 하는가?
from itertools import product
N = int(input())
M = int(input())
num_list = set()
num_list.update(["0", "1", "2", "3", "4", "5", "6", "7", "8", "9"])
remain_list = []
if M != 0:
broken_list = set(map(str, input().split()))
# 0~9에서 입력받은 숫자들 제외하기
remain_list = num_list - broken_list
# M이 0인 경우 리스트 입력 없음 주의
else:
remain_list = num_list
# 사용 가능한 번호 리스트
remain_list = list(remain_list)
remain_list.sort()
min_cnt = 0
# [1] 100에서 +, -눌러서 이동하기
min_cnt = abs(100 - N)
# [2] 번호 새로 입력하고, +,- 눌러서 이동하기
N_str = str(N)
N_len = len(N_str)
# 1) N(목표 채널)의 길이가 2 이상인 경우
if N_len >= 2:
# N_len - 1, N_len, N_len + 1 자릿수의 가능한 모든 수 구하기
for i in range(N_len - 1, N_len + 2):
# 현재 최소값보다 자리수 i 가 같거나 더 크다면 볼 필요 X (어차피 최소값이 될 수 없음)
if i >= min_cnt:
continue
# 중복 순열!
permus = product(remain_list, repeat=i)
# permus = list(permus) # 제너레이터를 list로 변환하면 모두 메모리에 올라가서 메모리 초과남 주의!! list 변환 없이 제너레이터 그대로 순회하면 됨!
for elem in permus:
# 각 조합을 정수로 변환하기
elem_list = list(elem)
elem_list = "".join(elem_list)
num = int(elem_list)
# 두 수의 차이(+ or - 눌러야 하는 횟수) 계산 후 꼭 i 더하기! (해당 숫자를 만들기 위해 i번 버튼을 누르는 것이므로)
elem_cnt = abs(N - num) + i
# 최소값 갱신
if elem_cnt < min_cnt:
min_cnt = elem_cnt
# 2) N의 길이가 1인 경우
else:
# N_len, N_len + 1 자릿수의 가능한 모든 수 구하기
for i in range(N_len, N_len + 2):
# 현재 최소값보다 자리수 i 가 같거나 더 크다면 볼 필요 X (어차피 최소값이 될 수 없음)
if i >= min_cnt:
continue
# 중복 순열!
permus = product(remain_list, repeat=i)
# permus = list(permus) # 제너레이터를 list로 변환하면 모두 메모리에 올라가서 메모리 초과남 주의!! list 변환 없이 제너레이터 그대로 순회하면 됨!
for elem in permus:
# 각 조합을 정수로 변환하기
elem_list = list(elem)
elem_list = "".join(elem_list)
num = int(elem_list)
# 두 수의 차이(+ or - 눌러야 하는 횟수) 계산 후 꼭 i 더하기! (해당 숫자를 만들기 위해 i번 버튼을 누르는 것이므로)
elem_cnt = abs(N - num) + i
# 최소값 갱신
if elem_cnt < min_cnt:
min_cnt = elem_cnt
print(min_cnt)
