[백준 1107번] 리모컨 - 파이썬

https://www.acmicpc.net/problem/1107

 

💡문제 분석 요약

수빈이는 TV를 보고 있다. 수빈이는 채널을 돌리려고 했지만, 버튼을 너무 세게 누르는 바람에, 일부 숫자 버튼이 고장났다.

리모컨에는 버튼이 0부터 9까지 숫자, +와 -가 있다. +를 누르면 현재 보고있는 채널에서 +1된 채널로 이동하고, -를 누르면 -1된 채널로 이동한다. 채널 0에서 -를 누른 경우에는 채널이 변하지 않고, 채널은 무한대 만큼 있다.

수빈이가 지금 이동하려고 하는 채널은 N이다. 어떤 버튼이 고장났는지 주어졌을 때, 채널 N으로 이동하기 위해서 버튼을 최소 몇 번 눌러야하는지 구하는 프로그램을 작성하시오.

수빈이가 지금 보고 있는 채널은 100번이다.

💡알고리즘 설계

1. 부서진 버튼을 집합으로 입력받는다.

2. +혹은 -만 눌러서 채널을 이동했을 때 값(원하는 채널에서 100을 뺀 값의 절대값)을 최소값으로 정한다.

3. 1에서 1000000까지 내가 누른 버튼의 값을 설정한다,

4, 내가 누른 버튼을 하나씩 검사하며, 만약 부서진 버튼이 포함될 경우 break한다.

5. 내가 누른 버튼에 부서진 버튼이 포함되지 않을 경우, 현재 최소값과 원하는 채널에서 내가 입력한 값을 뺀 절대값에 버튼을 누른 횟수를 더한 값 중에 더 작은 값을 최소값으로 정한다.

6. 최소값을 정답으로 출력한다.

💡코드

import sys
input = sys.stdin.readline

target=int(input())
M=int(input())

if M!=0:
    brokenBtn = set(map(int,input().split()))
else:
    brokenBtn=set()

minCount=abs(target-100)

for myInput in range(1000001):
    myInput=str(myInput)

    for i in range(len(myInput)):
        if int(myInput[i]) in brokenBtn:
            break
    else:
        minCount=min(minCount, abs(target-int(myInput))+len(myInput))

print(minCount)

💡시간복잡도

내가 누른 버튼이 부서진 버튼에 포함되는지 확인할 때, 접근을 빠르게 하기 위해 set을 사용했다.

범위를 1에서 1000000으로 정한 이유: 원하는 채널이 500000인데, 0,1,2,3,4,5,6,7,8이 부서졌을 경우 500000보다 큰 값인 999999를 입력 한 후 -버튼을 눌러 이동해야한다.

💡 느낀점 or 기억할 정보

브루트포스는 복잡하게 생각하지 말고 모든 범위를 다 고려해야한