[백준 문제] 1107번 리모컨 (파이썬)

코딩 프로세스 로직

초기 집합 구성

• 가능한 숫자(enable_set) 집합을 만든다. (집합을 만든 이유 : set이 list보다 빠르다 판단 및 중복 순서 상관 없으니)
  • 고장난 숫자가 없을경우 : M = 0
  • 고장난 숫자가 있을경우 : M > 0

실제 계산하기

• 답(result)에 가기 위해서는 두가지의 방법이 있다.
  • 직접 숫자를 쳐서 다이렉트로 답을 찾는 방법
  • 현 숫자에서 up/down 를 통해 가는법
  • 다이렉트로 할 수 없어서 직접 숫자 + up/down를 통해 가는 법

• 초기 result 값은 바로 up/down 로 갈 수 있게 세팅

• 브루트포스(완전탐색)의 핵심은 전체를 다 돌려보는 것이고 시간 복잡도도 10^6이 나오니까 그렇게 무리되는 부분은 아니라고 생각든다. <- O(1) 복잡도이라고 하더라 스터디원분들이!! 난 O(N)인 줄 알았는데!!
  
  모든 경우에 대해서 10^6번 돌리기 때문에 O(1)인것 같다고 하셨다. 참고:시간복잡도

• 고장난 숫자값이 들어갔을 때는 break하고 돌리는 식으로 짰다.

• 마지막에 현 result값과 새로운 result값을 비교해서 작은 걸로 하였다.

enable_set = {str(x) for x in range(10)}

N = int(input())
M = int(input())
if (M == 0):
    pass
else:
    break_set = set(input().split())
    enable_set -= break_set

result = abs(N - 100)
for i in range(1000001):
    is_true = True
    for part_num in str(i):
        if (part_num not in enable_set):
            is_true = False
            break
    if is_true is True:
        result = min(result, abs(N - i) + len(str(i)))

print(result)