[백준] 1107. 리모컨 / python 파이썬

🚩 브루트포스

 

thinking

아악 진짜 이거 계속 틀려서 구글링해봤다

나는 N의 최대 범위가 500,000이라 500000까지만 체킹하면 된다고 생각했는데 다른사람들은 다 range를 100만으로 잡는게 진짜 이해가 안갔다. 

50만 채널까지 존재하기 때문에 50만보다 크면서 모든 숫자의 경우를 거치는 100만까지를 범위로 잡았다는데 도대체 이게 뭔말이야 😑

뭔말이냐면 내가 이동하고 싶은 채널이 N(0~500,000) 번이라고 했을 때, 0번부터 ++로 이동하는 경우와 999,999번부터 --로 이동하는 경우(누를 수 있는 버튼이 9만 있으면 9밖에 못누르기 때문)를 전부 고려한 것이었다.

가능한 숫자를 하나하나 전부 순회하면서 누를 수 있는 숫자에 해당하는 경우만 조건문 처리를 통해 최소 갭을 계산해줬다.

 

 

맞은 코드 (success)

N = int(input())  # 채널번호
M = int(input())  # 고장난 버튼의 개수
remote = {str(x) for x in range(10)}  # 리모컨버튼

if M != 0:
    remote -= set(input().split())  # 사용가능한 버튼 뽑아냄

min_cnt = abs(100-N)  # 일단 100과의 갭을 최소로 두고 계산

for k in range(1000000):
    num = str(k)
    for i in range(len(num)):
        if num[i] not in remote:  # 0~999999까지의 숫자 순회하면서 리모컨 버튼에 없으면 패쓰
            break
        if i == len(num)-1:  # 마지막 자리수까지 확인했으면 최소 카운팅 갱신
            min_cnt = min(min_cnt, abs(N-k)+len(num))

print(min_cnt)

 

 

실패 코드 (Fail)

나는 처음에 순회 안하고 풀었는데 내가 잘못 생각한거였다.

testcase 3번을 보면, 500000일때 1,5번만 누를 수 있어서 '500000' 을 순회하며 누를 수 있는 버튼은 버튼 누르는 횟수에 더하기 1 해주고, 0처럼 누를 수 없는 버튼이면 가장 갭이 작은 1번 버튼을 눌러 그 차이를 계산해주는 방식으로 코드를 짰다.

문제에서 주어진 테스트케이스의 경우 이 코드로는 모두 정답이 나오지만, 아래와 같은 경우에서 문제가 생긴다.

예를들어 N=5478이고 6,7,8번이 못 누르는 버튼이라고 했을 때 5490일때가 가장 갭이 작은데 이 코드로 풀면 5459 또는 5499가 tmp의 가능성이 된다. 그럼 최소갭이 안된다.

range(1000000)을 순회하지 않고 이 코드를 살려 풀어보고 싶었으나 저 90과 78의 갭을 찾기 위해서는 하나하나 다 돌려보는게 맞는거 같다

N = input()  # 채널번호
M = int(input())  # 고장난 버튼의 개수
remote = {str(x) for x in range(10)}  # 리모컨버튼

if M != 0:
    remote -= set(input().split())  # 사용가능한 버튼 뽑아냄

gap100 = abs(100-int(N))  # 100과의 차이
min_gap = 10  # 사용가능한 버튼과의 최소 갭 구할 변수
cnt = 0  # 버튼 누르는 횟수
tmp = ''  # 채널간의 차이 구할 변수
for s in N:
    if s in remote:
        tmp += '0'
        cnt += 1
    else:
        for num in remote:
            gap = abs(int(num)-int(s))
            if gap < min_gap:
                min_gap = gap
        tmp += str(min_gap)
        cnt += 1

res = min(gap100, int(tmp)+cnt)
print(res)

 

 

후기

언제 골드 한번에 맞아보나 ~ 😑