백준 1107번 : 리모컨

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

🍘 1차 구현

처음 문제를 접했을 때에는 뒤에서 부터 숫자를 비교해주는 방법을 생각해보고 이를 코드로 구현해보았습니다.
물론 100번에서 시작하므로, 원하는 채널과 100을 뺀 절대값하고 비교해서 최소를 구하는 과정도 처리해보았습니다.

import sys
input = sys.stdin.readline
INT_MAX = sys.maxsize

channel = int(input()) # 원하는 채널
channelList = list(map(int, str(channel))) # 채널은 한글자씩 처리하기 위해 리스트로 관리 
num = int(input()) # 고장난 버튼의 개수
notWork = set() # 고장난 버튼을 set으로 빠르게 찾기 가능
if num != 0:
    kindBut = list(map(int,input().split())) # 고장난 버튼을 받기
    for i in kindBut:
        notWork.add(i)

firstCheck = abs(channel - 100)

idx = len(channelList)

secondCheck = INT_MAX
multi = 1
for i in range(idx):
    nowIdx = idx - i - 1
    check = int(channelList[nowIdx])
    count = 0
    while check in notWork:
        right = min(check + count, 9)
        left = max(check - count, 0)
        if right not in notWork or left not in notWork:
            secondCheck += count * multi
            break
        count += 1
    multi = multi * 10
    secondCheck += 1

print(min(firstCheck, secondCheck))

그런데 문제는 마지막 예제에서 생겼습니다.
하나씩 뒤에서부터 비교하고 해당 버튼이 고장나지 않았을 경우 눌러주는 것과 다른 숫자를 눌러서 + 혹은 -로 이동하는 것이 더 빠르게 접근할 수 있는 예외가 생기는 것 입니다.

🍙 2차 구현

그러다 지난 겨울 코테 대비 캠프에서 배운 시간 복잡도에 대해서 떠올렸습니다.
절대적인 것은 아니지만 대략적으로 for 문을 1억번 돌 때, 1초가 지난다는 것인데, 해당 문제는 2초의 시간이 주어졌고, 전체 경우가 1억번이 되지도 않았습니다.
그러니 즉, 간단하게 생각해서 단순한 for문만을 활용해서 문제를 풀 수 있다는 것을 깨달았습니다.
(문제의 정답율이 낮다보니 너무 어렵게만 생각했던 것 같습니다..)

# 리모컨
## 고장난 리모컨이 주어졌을 때, 특정 채널로 이동하기 위한 최소의 버튼 클릭 횟수를 구하는 프로그램
## 참고로 현재 보고 있는 채널은 100번
### 입력 : 첫 줄에 원하는 채널, 두 번째 줄에 고장난 버튼의 개수, 마지막에 고장난 버튼의 종류가 입력
### 출력 : 버튼 클릭의 최소 횟수

import sys
input = sys.stdin.readline
INT_MAX = sys.maxsize

channel = int(input()) # 원하는 채널
channelList = list(map(int, str(channel))) # 채널은 한글자씩 처리하기 위해 리스트로 관리 
num = int(input()) # 고장난 버튼의 개수
notWork = set() # 고장난 버튼을 set으로 빠르게 찾기 가능
if num != 0:
    kindBut = list(map(int,input().split())) # 고장난 버튼을 받기
    for i in kindBut:
        notWork.add(int(i))

minVal = abs(channel - 100)
check = True

for i in range(1000001): # 1억 번을 도는 for문이 1초가 걸리므로 이 정도의 시간 복잡도는 충분히 for문으로 감당 가능
    iList = list(map(int,str(i)))
    for j in iList:
        if int(j) in notWork:
            check = False
            break
    if check:
        minVal = min(minVal,abs(channel - i) +len(iList)) # 매번 최소값을 갱신
    check = True 

print(minVal)

여러분은 저처럼 어렵게만 생각하지 말고 시간 복잡도를 먼저 생각하고 구현하시기 바랍니다 ㅜㅜ 저는 괜히 고생했네요..