1107(리모컨) - 해결

리모컨

 

문제

수빈이는 TV를 보고 있다. 수빈이는 채널을 돌리려고 했지만, 버튼을 너무 세게 누르는 바람에, 일부 숫자 버튼이 고장났다.

리모컨에는 버튼이 0부터 9까지 숫자, +와 -가 있다. +를 누르면 현재 보고있는 채널에서 +1된 채널로 이동하고, -를 누르면 -1된 채널로 이동한다. 채널 0에서 -를 누른 경우에는 채널이 변하지 않고, 채널은 무한대 만큼 있다.

수빈이가 지금 이동하려고 하는 채널은 N이다. 어떤 버튼이 고장났는지 주어졌을 때, 채널 N으로 이동하기 위해서 버튼을 최소 몇 번 눌러야하는지 구하는 프로그램을 작성하시오. 

수빈이가 지금 보고 있는 채널은 100번이다.

 

입력

첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다.  둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼이 주어지며, 같은 버튼이 여러 번 주어지는 경우는 없다.

 

출력

첫째 줄에 채널 N으로 이동하기 위해 버튼을 최소 몇 번 눌러야 하는지를 출력한다.

---

처음에는 해당 문제를 어떻게 구할 수 있을까 생각해보았는데 답이 없었다.

째든 가장 가까운 숫자를 찾는 방법을 찾고자 하였다.

하지만 특정 숫자를 찾는 것은 어려웠다.

그래서 보니 브루트포스 알고리즘에 해당하는 문제였다.

그래서 그냥 위에서 가장 가까운 숫자와 아래에서 가장 가까운 숫자를 찾고자 하였다.

그리고 이 두 숫자와 100에서 차이 중에서 가장 작은 숫자를 정답으로 하였다.

그 과정에서 M이 0 이거나 위와 아래 가장 작은 숫자가 없는 경우를 생각해주었다.

import sys
input = sys.stdin.readline

N = int(input().strip())

M = int(input().strip())

# M이 있을 경우에만 받기
not_list = []
if M != 0:
    not_list = list(input().split())

# N 위로 가장 가까운 숫자 찾기
up = -1
# 대강 1000000 정도까지 구하기
for i in range(N,1000000):
    # 각 자리 숫자가 안되는 숫자 버튼에 속하는지 판단
    for j in set(str(i)):
        if j in not_list:
            break
    # 만약 모든 숫자가 안 속한다면 해당 숫자를 선택
    else:
        up = i
        break

# N 아래로 가장 가까운 숫자 찾기
down = -1
for i in range(N,-1,-1):
    # 각 자리 숫자가 안되는 숫자 버튼에 속하는지 판단
    for j in set(str(i)):
        if j in not_list:
            break
    # 만약 모든 숫자가 안 속한다면 해당 숫자를 선택
    else:
        down = i
        break

# up과 down의 여부에 따라 판단
if up > -1 and down > -1:
    print(min(abs(N - 100),len(str(up)) + up - N,len(str(down)) + abs(down - N)))
elif up > -1:
    print(min(abs(N - 100),len(str(up)) + up - N))
elif down > -1:
    print(min(abs(N - 100),len(str(down)) + abs(down - N)))
else:
    print(abs(N - 100))