[알고리즘] 백준 1107 (파이썬)

이 문제는 완전탐색을 통해 정답을 구하는 문제이다.

'''
 내 풀이
 end를 기준으로 +,- 1씩 시켜서 조건을 만족하는 값까지 찾기

'''
end = int(input())
bn = int(input())
bl = []
if bn>0:
    bl = list(map(int, input().split()))

start =100
ans = 0


num = list(map(int,set(str(end))))

if end == 100:
    print(0)

elif bn == 10:
    print(abs(end-start))
else:

    er = 0
    for _ in num:
        if _ in bl:
            er+=1

    if er == 0:
        print(min(len(str(end)), abs(end-100)))

    else:
        n1 = end - 1
        n2 = end + 1

        while end != start:

            if n1>=0:
                a1 = list(map(int,set(str(n1))))
                err1 = 0
                for i in a1:
                    if i in bl:
                        err1 += 1
                if err1 == 0:
                    ans = n1
                    break

            a2 = list(map(int,set(str(n2))))
            err2 = 0
            for j in a2:
                if j in bl:
                    err2+=1
            if err2 == 0:
                ans =n2
                break

            n1-=1
            n2+=1

        print(min(abs(end-100), len(str(ans))+abs(ans-end) ))


'''
 다른 사람 풀이
 나올 수 있는 모든 채널을 처음부터 끝까지 탐색 --> 탐색할 때마다 최소값 업데이트
'''
N = int(input())
M = int(input())
btns = set()  # 고장난 버튼 집합
if 0 != M:  # 고장난 버튼 있으면 입력
    btns = set(input().split())
ans = abs(N - 100)  # 100부터 N으로 +나 -버튼 누른 횟수
for num in range(1_000_001):  # 0 ~ 1,000,000 채널 번호
    str_num = str(num)  # 채널 번호를 문자열로
    for n in str_num:  # 채널 번호의 한 자리씩
        if n in btns:  # 해당 자리가 고장난 버튼 숫자이면 종료
            break
    else:  # 채널 번호의 모든 자리가 고장나지 않은 경우
        print(num)
        ans = min(ans, len(str_num) + abs(num - N))
print(ans)
	

나의 풀이로 풀면 정답지점으로부터 탐색을 시작하기 때문에 모든 채널을 확인하는 것보다 확실히 빠른 속도가 나온다. 하지만 고려해야할 점이 몇가지 있었다.

1. 음수가 되면 안된다.

음수가 되면 a1 = list(map(int,set(str(n1)))) 부분에서 int로 mapping이 되지 않는다. 따라서 valueerror가 일어난다.
==> 음수가 아닐 때만 mapping 시키도록 조건문을 만든다.

2. 모든 번호가 고장날 경우에 무한루프가 돌 수 있다.

이 문제에서 모든 번호가 고장나면 계속 탐색하기 때문에 무한루프가 돌아간다.
==> 모든 번호가 고장나는 경우를 추가하여 조건문을 만든다.