리모컨

백준 1107번: 리모컨

아이디어

채널 0번부터 100만번까지 스르륵 돌면서 내가 숫자 눌러서 갈 수 있는 채널중에 가야하는 채널에 가장 가까운 채널을 찾는다. 그리고 100부터 +-버튼 눌러서 가는거랑 비교해서 출력.

코드

N = int(input())
M = int(input())

if M != 0:
    brokenButtons = set(map(int, input().split()))
else:
    brokenButtons = set()


def selectChannel(channel):
    dif = 987654321
    sel = 987654321
    for i in range(1000000):
        s = True
        for c in brokenButtons:
            if str(c) in str(i):
                s = False
                break
        if not s:
            continue

        # 갈 수 있는 채널
        if abs(channel - i) < dif:
            dif = abs(channel - i)
            sel = i

    return sel


selected = selectChannel(N)
bt = len(str(selected))
print(min(abs(N - 100), abs(selected - N) + bt))

여담

EOFError는 고장난 버튼이 한개도 없는데 입력을 받으려고 해서 에러가 난 듯 하다. 고장난거 없으면 입력 안받게 수정하니까 잘 돌아간다.

맨 처음에는 채널 처음부터 탐색하면 당연히 시간초과 날 줄 알고 문자열 쪼개서 가장 가까운 채널을 찾다가 포기했다. edge case가 넘 많다. bruteforce 태그 달려있는데 왜그랬지?