[BOJ / Python] 1107번 : 리모컨

문제 제목, 난이도

1107번 : 리모컨, 골드5

---

문제 링크

www.acmicpc.net/problem/1107

1107번: 리모컨

---

코드(Python)

import sys
input = sys.stdin.readline

n = int(input())
m = int(input())

ava = []
available = [True] * 11

if m != 0 :
    li = list(map(int,input().split()))
    for i in li :
        available[i] = False

for i in range(0, 10) :
    if available[i] == True :
        ava.append(i)

ans = abs( 100 - n )

for i in range(0, 1000000) :
    tmp = True
    i_str = str(i)

    for j in i_str :
        if available[int(j)] == False :
            tmp = False
            break
    
    if tmp == True :
        ans = min(ans, abs(i - n) + len(str(i)))

print(ans)
    

---

풀이

고장난 버튼의 개수가 0 이면 고장난 버튼 리스트를 입력받지 않습니다.

초기값은 +, - 버튼만을 이용해서 이동하는 방법입니다.

0부터 1,000,000 까지 숫자에 대하여 각 자리수가 available 한 숫자들로 이루어져 있는지 확인하고 한 자리라도 사용 불가능한 경우 다음 숫자를 확인하고, 모든 숫자가 available 할 경우 그 채널 숫자를 누르는 버튼 카운트 ( len(str(i)) ) 와 + 또는 - 버튼을 누르는 카운트를 더한 다음 지금까지의 값과 비교합니다.

n의 범위가 0 <= n <= 500,000 이었기 때문에 999,999 에서 500,000에 접근할 경우가 i 값의 최대라고 판단하여 1,000,000 까지 루프를 돌렸습니다.

---

체크리스트

브루트포스

처음에는 목표 채널을 스트링으로 변환해서 각 자릿수를 다루는 방법으로 접근해보려고 했는데, 진행할수록 반례가 많아지길래 방식을 바꿨다.

제한시간이 2초라서 1000000 * 숫자 버튼의 수 10 을 해도 한참 시간이 남아서 (1억을 1초라 하면) 범위의 숫자를 하나씩 다 체킹해도 정답처리를 받을 수 있는 문제이다.

백만개의 값을 갖는 boolean 리스트를 만들고 전부 available 한 숫자로 이루어져있는지 확인해서 True , False 값을 준 다음 리스트의 인덱스 i 에서 왼쪽 오른쪽으로 한 칸씩 확인하면서 값이 True인 인덱스를 찾는 방법도 있을 수 있겠다. 이 방법을 쓰면 찾았을 때 min 연산을 한 번만 쓰면 될 듯 ?

리모콘은 새로 사자