[백준] 1107번 리모컨, 파이썬 문제 풀이

문제

백준 1107번 리모컨 문제를 해결했습니다. 

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

1107번: 리모컨

문제

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

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

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

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

입력

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

출력

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

 

문제 풀이

이번 문제는 브루트 포스(Brute Force) 알고리즘으로 해결하는 문제입니다. 우리말로 완전 탐색이라고 하는데, 그냥 반복문을 사용해서 모든 경우의 수를 찾는 방법입니다.

 

문제를 읽었을 때, 완전 탐색을 사용하는 것은 꺼려집니다. 더 좋은 방법이 있을 것만 같아 찝찝하기 때문입니다. 하지만, 아무리 생각해도 다른 알고리즘이 생각이 나지 않아서 스스로 풀이 방법을 생각했습니다.

 

최초에 생각한 방법은 다음과 같습니다. 수빈이가 보고자 하는 채널 N의 각 자릿수를 고장나지 않은 숫자 중 가장 가까운 숫자를 골라 N과 가장 가까운 숫자를 만드는 것입니다. 그리고 나서 +, -를 눌러 N까지 이동하는 방법입니다. 이 연산의 결과와, 그냥 100번부터 +,-를 눌러 이동하는 것 중 작은 것을 찾으려고 했습니다.

 

해당 코드는 다음과 같습니다.

N = input()
num = int(input())
if(num > 0):
    breakNum = list(map(int,input().split()))
else: #고장난버튼없으면 걍 이동
    print(len(N))
    exit(0)

result = 0

#버튼
button = []
for i in range(10):
    button.append(i)

j=0
idx = []
##고장난 버튼 제거하기
while(j<num):
    for i in breakNum:
        for k in button:
            if (i==k):
                idx.append(k)
                j+=1
idx.sort(reverse=True)
for l in idx:
    button.pop(l)

#버튼 다 고장난 경우 +,-만 눌러서 이동
if(len(button)==0):
    print(abs(int(N)-100))
    exit(0)

n = ""

#사용할 수 있는 버튼을 이용해 N과 가장 근접한 숫자 찾기
for i in N:
    tmp = button.copy()
    for j in range(len(tmp)):
        tmp[j]=abs(tmp[j]-int(i))
    n += str(button[tmp.index(min(tmp))])

result = len(n)+abs((int(N)-int(n)))

#+,-를 눌러 이동한 것과 비교해서 더 적은 방법을 선택
if (abs(int(N)-100) > result):
    print(result)
else:
    print(abs(int(N)-100))

 

이 방법은 제 생각이 짧았습니다. 마지막 7번째 예시를 보면 주어진 N은 80000, 고장난 버튼은 8, 9 입니다. 이 때, 만들어져야 하는 숫자는 77777 이고, 2223번 +를 눌러 채널을 이동해야 합니다.

제 풀이대로 하면, 70000이 나오게 됩니다. 각 자릿수마다 비교하기 때문에 둘째자리부터 0과 비교해서 가장 가까운 숫자는 0이기 때문입니다.

 

이렇게 되면, 결국 풀이는 모든 숫자를 찾아봐야 하는 수밖에 없습니다. 다른 조건들을 추가해서 일부 숫자만 검사하는 것이 더 비효율적이기 때문입니다. 제가 작성했던 코드는 반복문이 많아서 딱 봐도 시간 초과가 날 것 같았습니다. 그렇기 때문에, 다른 사람들의 풀이를 참고했습니다.

N = int(input())
brokenNum = int(input())

if(brokenNum > 0):
    brokenButton = list(map(int,input().split()))
else: #고장난버튼이 없으면 바로 이동
    print(len(str(N)))
    exit(0)

result = abs(N-100)

for tmp in range(1000001):
    tmp = str(tmp)
    for i in range(len(tmp)):
        if (int(tmp[i]) in brokenButton):
            break
        elif (i==len(tmp)-1): #마지막 자리까지 오면 비교
            result = min(result, abs(int(tmp)-N)+len(tmp))

print(result)

우선, 탐색 범위는 0~1000000까지 입니다. 수빈이가 원하는 채널은 50만까지 있지만, 50만보다 더 높은 채널로 이동해서 -를 눌러 내려오는 것이 더 빠를 수도 있기 때문입니다. 

 

제가 참고한 부분은 if(int(tmp[i] in brokenButton) 입니다. in 문법을 반복문에만 사용하다보니, 조건문에 사용할 수 있다는 것을 깜빡했습니다. 해당 문법을 사용하지 않고 중첩 반복문을 작성하면, break를 사용해도 완전히 벗어날 수 없어 너무 많은 연산을 하게 됩니다.

 

정리

브루트 포스 알고리즘은 많이 풀어보지 않아서 조금 낯설었습니다. 거부감이 많이 드는 만큼, 많은 문제를 풀어보고 적합한 상황에만 사용할 수 있는 능력을 길러야 할 것 같습니다.