백준[Python] - 1107 : 리모컨

문제

1107번: 리모컨

풀이

나의 풀이

문제에서 주어진대로 채널의 수는 무한대이지만, n의 범위는 500000 이하이므로 '완전 탐색'의 방법을 사용했다.

1. 탐색하는 범위를 1e6까지 하면, n=5e5일 때에도 모든 경우를 고려할 수 있기 때문에 탐색 범위를 1e6으로 설정하였다.
2. 0~1e6까지의 모든 채널에서 리모컨으로 접근 가능한 채널의 경우는 n과의 거리를 채널과 함께 리스트에 저장
3. 리스트 정렬
   1. n과 선택 가능한 채널의 거리
   2. 선택 가능한 채널의 자리수(적을 수록 유리하기 때문)
4. 리스트에 저장된 가장 가까운 채널에서 1씩 움직여 n으로 도달하는 경우 vs 100에서 n까지 1씩 움직여 도달하는 경우 판단

# 리모컨
import sys
input = sys.stdin.readline
n = int(input().strip())
m = int(input().strip())
broken = list(map(int, input().strip().split()))
if n==100:
    print(0)
else:
    if m==0: # 고장난 버튼 없는 경우
        if abs(n-100)>len(str(n)): 
            print(len(str(n)))
        else: # +/-누르는게 더 빠를 경우
            print(abs(n-100))
    elif m==10: # 전부 고장난 경우
        print(abs(n-100))
    else:
        lst = []
        for i in range(int(1e6)):
            nums = list(map(int,list(str(i))))
            if set(nums).intersection(set(broken)):
                continue
            else:
                lst.append((abs(n-i),i))

        lst.sort(key=lambda x:(x[0],len(str(x[1])))) # n과의 거리는 같지만, 눌러야하는 번호가 더 적은 경우 순으로 정렬

        # 누를 수 있는 번호가 없는 경우/그렇지 않은 경우
        if lst:
            dist, channel = lst[0]
        else:
            dist, channel = abs(n-100), 100

        if dist+len(str(channel))<abs(n-100):
            print(dist+len(str(channel)))
        else:
            print(abs(n-100))

min 함수를 사용했으면 보기 더 편했을 것 같다.

다른 풀이

로직 자체는 같지만 코드의 차이가 존재하는 것 같다

target = int(input())
ans = abs(100 - target)
M = int(input())
if M:
    broken = set(input().split())
else:
    broken = set()

for num in range(1000001): 
    for N in str(num):
        if N in broken:
            break
    else:
        ans = min(ans, len(str(num)) + abs(num - target))

print(ans)