[알고리즘][파이썬] 백준 1107번 - 리모콘

문제 링크 : https://www.acmicpc.net/problem/1107

---

처음 떠올렸던 접근 방법

1. 이동하려는 채널의 각각의 자리를 확인하여 입력 가능한 숫자이면 바로 입력한다.
2. 입력이 불가능한 숫자이면, 입력 가능한 숫자 중 최대한 차이가 적은 숫자를 입력한다.
3. 최종적으로 완성한 숫자와 이동하려는 채널의 차이를 계산한다.
4. 버튼 입력횟수 + 채널의 차이를 더해 출력한다

내가 처음에 생각했던 접근 방법으로 문제를 푸니, 예제 입력은 모두 정상적으로 나왔는데 코드를 제출하니 런타임 에러가 발생했다.
입력값 중에 예외가 발생하는 경우가 있었던 것 같은데, 수정하려고 여러번 노력했지만 결국 실패하여 다른 사람들의 코드를 참고했다.

개선된 접근 방법

1. 0부터 100만까지 모든 수들을 순회한다.
2. 현재 순회중인 채널의 각 자리수를 조회한다.
3. 순회중인 채널이 모두 입력 가능하면 최소 입력횟수를 비교하고, 입력 불가능하면 다시 순회한다.

---

최종 입력 코드

target = int(input())
M = int(input())
numberList = {str(i) for i in range(10)} # 입력 불가능한 번호들을 제거해주기 위해 리스트가 아닌 set로 선언

if M != 0:
    numberList -= set(map(str, input().split())) # 입력 불가능한 숫자들 제외

start = 100
count = abs(start - target) # 모든 숫자가 입력이 불가능할 경우(+, - 로만 이동하는 경우)가 입력 횟수 최대의 경우 이므로
                            # 입력 횟수를 저장하는 변수를 최대의 경우로 선언

for i in range(1000000): # 고장날 버튼과 희망채널의 관계를 고려하여 최악의 경우 100만까지 순회해야하므로 범위를 100만까지 지정
    for j in range(len(str(i))): # 현재 순회중인 채널의 각 자릿수를 조회
        if str(i)[j] not in numberList: # 현재 자릿수의 숫자가 입력 불가능한 숫자이면 다시 순회하러 감
            break
        elif j == len(str(i)) - 1: # 모든 자릿수가 입력 가능한 숫자이면
            count = min(count, abs(i - target) + len(str(i))) # 이전에 구한 입력 횟수보다 적다면 최소 입력횟수를 변경

print(count)

코드를 참고할 때 이해가 안됐던 부분이,

1. 입력횟수를 100만까지 지정하는 것
2. 자릿수를 조회할 때 else가 아니라 elif를 사용하는 것

두 가지 였다.

입력횟수를 100만까지 지정하는 것은, 문제에서 채널은 무한대라고 했기 때문에 만약 이동하고자 하는 채널이 40만일 때, 고장난 버튼이 [1, 2, 3, 4, 5]일 경우, 채널을 60만으로 이동한 후 -를 하여 이동하는 것이 최선의 이동 방법이기 때문이다.

자릿수를 조회할 때 elif를 사용하는 이유는, 만약 else로 사용한다면 순회중인 채널의 모든 각 자릿수를 조회하기전에 끝나버리기 때문이다.
elif j == len(str(i)) - 1로 설정을 해야 모든 자리수를 다 조회할 수 있다.

---

문제를 풀 때 한 가지 접근 방법 뿐만 아니라, 다양한 각도에서 접근 방법을 떠올려야겠다는 생각을 갖게 된 문제였다.