[Python] G5_1107_리모컨 📺

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

문제

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

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

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

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

입력

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

출력

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

예제

조건

• 시간 제한: 2초
• 메모리 제한: 256MB

코드

from itertools import product
import sys
input = sys.stdin.readline

# 입력
go_num = input().rstrip()
out_cnt = int(input())
# 고장난 버튼이 없는 경우 (=10개 모두 동작)
if out_cnt == 0:
    result = min(len(go_num), abs(int(go_num) - 100))
    print(result)
    exit(0)
# 모든 버튼이 고장났을 경우
elif out_cnt == 10:
    a = set(input().rstrip().split())
    print(abs(int(go_num) - 100))
    exit(0)

out_lst = set(input().rstrip().split())
lst = set(str(i) for i in range(10))
lst -= out_lst  # 차집합을 이용하여 사용가능한 버튼을 파악함
up_down = abs(int(go_num) - 100) # 초기 채널인 100번에서 +- 이동하는 경우
minNum = sys.maxsize

for a in range(-1,2): # 중복순열의 원소 가지수를 3가지 경우로 파악함
    if a == -1:
        if '0' in lst or len(go_num) == 1:
            continue
    for i in product(lst,repeat=len(go_num)+a):
        num = ''
        for j in i:
            num += j
        
        diff = abs(int(go_num) - int(num))  # 가고자 하는 채널과의 차이
        click = len(str(int(num)))  # 버튼을 누른 횟수 
        diff += click
        if minNum > diff:
            minNum = diff

# 출력
result = min(minNum, up_down)
print(result)

1. out_cnt 가 0 일 경우와 10 일 경우를 미리 고려한다.

• 모두 동작하는 경우라도, 버튼을 직접 눌러서 가는 것보다 초기 채널 100 번에서 +,- 로 이동하는 것이 빠를 수 있기 때문이다.

• Ex) 채널 101 으로 가고자한다면, + 로 1번이면 가능하지만, 101 을 직접 누른다면 3번의 동작이 필요하다.

• 모든 버튼이 고장났다면, +,- 로 이동하는 방법 밖에는 존재하지 않는다.

2. 차집합을 사용하여 lst 에 사용가능한 버튼만 남겨준다.

3. 초기 채널 100 번에서 +,- 으로 이동하는 경우인 up_down 변수를 만든다.

4. go_num 의 길이에 -1,0,+1 한 중복순열도 고려해준다.

• 0 번 버튼이 고장났고, 가고자하는 채널의 숫자가 한자리 수가 아니라면, -1 의 경우도 고려한다.

• 0 번 버튼을 사용할 수 있다면, 굳이 고려해주지 않아도 자동적으로 여러 자리수를 파악할 수 있기 때문이다.

• go_num 이 1555이고, 사용할 수 있는 버튼이 2,8 뿐이라고 가정해보자.

• 만약 go_num 의 길이인 4로만 중복순열을 만든다면, 근사치는 2222 가 나와 abs(1555-2222) + len(num) 으로 671이라는 답이 나올 것이다.

• 하지만 go_num 의 길이보다 하나 작은 3으로 중복순열을 만든다면, 근사치는 888 이 나와 abs(1555-888) + len(num) 으로 670이라는 답이 나오게 된다.

• 동일한 이유로 go_num 의 길이보다 하나 큰 숫자로도 중복순열을 만들어 파악해준다.

5. 이러한 과정을 거쳐서 나온 diff 값에 버튼을 누른 횟수인 click 을 더해 최종적으로 minNum 을 알아낸다.

6. 마지막으로 미리 만들어 둔 up_down 변수와 비교를 한 후에 더 작은 값을 출력해준다.

느낀 점 & 배운 점

1. 생각보다 고려해야할 점들이 너무 많아서 꽤나 시간이 오래 걸렸던 문제이다. 다른 사람들이 올려준 반례들이 없었다면 해결하기가 힘들었을 것 같다.. 이번에는 반례를 다 넣어보며 수정을 했지만 만약 실전이라면 내가 직접해야 할텐데 쉽지 않을 듯하다. 다음부터는 반례를 직접 찾아서 해결해보는 연습도 해보아야겠다!

2. 브루트포스 문제라 그런지 엣지 케이스들이 상당히 많았다.. 그래도 수정 끝에 해결을 했다는 점에서 뿌듯함을 느낀다!