[백준] 1107 리모컨(Python)

백준 - 1107 리모컨

문제

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

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

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

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

입력

첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼이 주어지며, 같은 버튼이 여러 번 주어지는 경우는 없다.

출력

첫째 줄에 채널 N으로 이동하기 위해 버튼을 최소 몇 번 눌러야 하는지를 출력한다.

예제

---

풀이

1. 접근

• 브루트포스 알고리즘
• 출력: 이동하려는 채널과 가장 가까우면서, 고장난 버튼 목록에 없는 숫자들로 이루어진 수

➡️ 모든 수를 탐색하면서, 해당 숫자의 각 자릿수에 접근해서 고장난 버튼 목록에 포함되어 있는지 확인해야 함

2. 주의할 점

• 이동하려고 하는 채널의 범위: 0 <= N(dest) <= 5,000,000
• 채널의 전체 범위: 무한대

➡️ N의 범위와 무관하게 채널이 무한대이기 때문에 50만 이상의 채널번호에서 N(dest)로 이동 가능
➡️ 탐색의 범위 설정은 50만이 아닌, 100만까지
➡️ N의 범위 이상의 채널에서 접근하는 경우가 발생하므로 절댓값을 계산하는 것이 필수적!!!!!!!!

ex) N: 4,999,999 / M: 4 / broken: 0, 4, 8, 9 인 경우

3,777,777 에서 접근하는 것보다 5,111,111 에서 접근하는 것이 빠름

➡️ N의 범위 이상의 범위에서 접근!
➡️ N의 범위 * 2 만큼의 탐색범위 필요

---

코드

from sys import stdin

MAX = 10 ** 6
dest = int(input())
num_of_broken = int(input())
broken = []

# 고장난 버튼의 개수가 0이 아닌 경우
if num_of_broken:
	broken = stdin.readline().split()

if dest == 100:
	print(0)
else:
	# moves 초기값: dest에서 + or - 로만 이동하는 경우
	moves = abs(dest - 100)
    
    # 0 - 1,000,001 까지의 범위 탐색
	for channel_int in range(MAX + 1):
		channel = str(channel_int)
        
        # channel의 각 자릿수에 접근 
		for idx, ch in enumerate(channel):
        	# broken에 포함된 숫자이면 break
			if ch in broken:
				break
            
            # broken에 포함되지 않고 모든 자릿수까지 탐색한 경우
			elif idx == len(channel)-1:
            	# ex) dest: 5457, num_of_broken: 3, broken: 6, 7, 8
                # 5455 or 5459 에서 접근하는 것이 빠름
                # (5457 - 5455) + 4(5455가 네자리)
                # (dest - channel) + len(channel)
                # channel값이 매번 바뀌기 때문에 최솟값을 저장해두고 비교해서 가장 작은 값을 도출해야함
				moves = min(moves, abs(dest-channel_int)+len(channel))
	print(moves)

---

실수 포인트

1. 범위를 숫자로 쓰는 게 헷갈릴 것 같아서 MAX 로 정의해놓고 썼는데 그 마저도 틀렸다... 1백만으로 초기화했어야 했는데 0이 하나 더 붙어서 1천만이 됐다......... 시간초과 두 번 뜨고 한참만에 알았다 ^^....

2. int str 캐스팅 오류
   아직도 왜 오류났던 건지 잘 모르겠다.
   int 타입 변수 channel을 str 타입으로 바꿔서 쓰고 싶었는데 channel = str(channel) 코드가 먹히질 않았다. 이리저리 시도하다가 그냥 변수 이름을 바꿔서 작성함.. ㅠ

3. len(str(channel)) 도 먹히질 않았다. int 타입이라서 len이 안먹는다고 str이 아니라고 에러 표시가 계속 떴다... 어쩌라고... str으로 덮었는데... 이것도 안 돼? ㅠ............ 진짜 어쩌라고 x 1000000000번 외쳤다.. ㅋ..... 2번 실수부터 고치고 자연스럽게 해결했다 ^^.......................

4. 분명히 min 함수를 씌웠는데 왜 숫자가 점점 커지지? 역시 컴퓨터는 바보다 min 함수 다시 짜야하나? ➡️ 응 내가 틀렸어~~ 그저 코드를 잘못짜서 값이 제대로 안나왔다. 역시 바보는 나인거로^^~

약간 눈물이 날라는데 괜찮아......... 오늘의 1커밋..... 이미 다음날 새벽이지만(심지어 4시)..... 완......🥹