[baekjoon] 1107. 리모컨 문제풀이 with Python

1107. 리모컨

1107번: 리모컨

코딩 테스트 문제 풀이의 첫 게시글로는 알고리즘 이론에 포스팅했던 브루트 포스 알고리즘을 활용하는 여러 문제들 중 유명한 문제인 골드5 문제 리모컨에 대한 풀이를 들고 왔다.

 

---

나의 풀이

vscode로 작성한 화면

 

# 1107. 리모컨 (골드 5)
# 알고리즘 분류 : 브루트포스

import sys
n = int(sys.stdin.readline())
m = int(sys.stdin.readline())
broken = []
if m > 0 :
    broken = list(map(int, sys.stdin.readline().split()))

# 가고자 하는 채널까지 + 혹은 - 만 눌러 가는 값을 가장 디폴트 값으로 선정
result = abs(n - 100)

# 0 ~ 1,000,000 까지의 모든 정수를 브루트포스
# 여기서 최대 채널인 500,000까지가 아닌 1,000,000 까지 브루트포스를 하는 이유는,
# 가고자 하는 채널이 500,000까지이지 채널은 무한대로 존재하기 때문.
# 즉, 500,000번으로 가고 싶지만 3, 4, 5가 고장난 경우에는 299,999번에서 +를 200,001번 누르는 것이 아닌
# 600,000번에서 -를 100,000번 누르는 것이기 때문.
for num in range(1000001) :

    # 고장난 버튼이 하나라도 있다면 해당 채널은 +- 검사가 필요 없으므로 break
    num = str(num)
    for i in range(len(num)) :
        if int(num[i]) in broken :
            break

        # 고장난 버튼이 없었다면, 해당 채널에서 +- 를 눌러 원하는 채널까지 가는 버튼 수를 구함
        # 이후 result와 비교하여, 적다면 result를 교체
        elif i == len(num) - 1 :
            result = min(result, len(num) + abs(n - int(num))) # num 채널을 누르는데 든 횟수와 +- 를 누르는데 든 횟수

print(result)

 

풀이 해설

나 또한 프로그래밍 초보이며, 계속해서 개발을 공부하는 입장이다.

따라서 다른 프로그래밍 초보도 쉽게 이해할 수 있도록, 최대한 쉽게 풀이를 써보려고 한다.

 

우선, 문제에서 원하는 입력사항을 받도록 한다.

import sys
n = int(sys.stdin.readline())
m = int(sys.stdin.readline())
broken = []
if m > 0 :
    broken = list(map(int, sys.stdin.readline().split()))

수빈이가 이동하려는 채널 N과 고장난 버튼의 개수 M을 입력받고,

만약 고장난 버튼이 하나라도 있는 경우에는 고장난 버튼을 여러개 입력받는다.

 

하지만 우리가 아는 파이썬 입력문인 input()과는 조금 다른 형태의 입력문이 있다.

바로 sys.stdin.readline() 이다.

이에 관한 내용은 후에 따로 포스팅하도록 하고, 지금은 input()보다 sys.stdin.readline()이 조금 더 빠르게 입력을 처리하는 명령어라는 것만 이해하고 넘어가도록 하자.

 

broken = [] 으로 빈 리스트를 굳이 먼저 만든 이유는,

이후 계속해서 broken 배열을 확인하도록 로직을 제작할 예정인데

만약 고장난 버튼이 없어 broken배열 자체가 존재하지 않게 된다면 없는 배열을 참조하려는 문제가 생기기에

우선 빈 배열을 만들어두는 것이다.

 

다음으론, 가고자 하는 채널까지 + 혹은 - 만 눌러 갈 수 있는 값을 디폴트로 둔다.

result = abs(n - 100)

이 값을 디폴트로 두는 데엔 이유가 있다.

 

만약 n번 채널에 가고 싶다면, 가장 빠르게 해당 채널로 갈 수 있는 방법이 무엇일까?

그것은, n번 채널에 가기 위한 버튼이 하나도 고장나있지 않은 채로 n번 채널의 숫자를 모두 누르는 것이다...

 

라고 이해했다면 틀렸다. 이 생각엔 몇 가지 반례가 존재한다!

바로, 99번 채널 혹은 101번 채널에 가는 반례이다.

 

리모컨으로 99번 혹은 101번에 가기 위하여

'9' 와 '9', 혹은 '1' 과 '0' 과 '1' 을 눌러 총 2번 내지 3번 버튼을 누르는 것보단,

그냥 - 혹은 + 를 한 번 누르는 게 더 버튼을 적게 누르기 때문이다!

이건 수빈이가 현재 100번 채널에 존재한다는 것을 잘 알아야 생각할 수 있는 반례이다.

 

이후 result보다 더 적게 버튼을 누르는 방법이 나타난다면, 그 때 result의 값을 바꿔치기하도록 로직을 구상할 것이다.

 

이제, 본격적으로 메인 로직에 들어간다.

for num in range(1000001) :

어라, 이 코드, 1,000,000번이나 for문을 돌린다.

분명 문제에서는 가고자 하는 채널로 입력받을 수 있는 채널은 500,000번이 최대라고 했는데?

 

바로 이 부분이, 리모컨 풀이에서 가장 많이 실수하게 되는 핵심 포인트이다.

 

문제를 잘 확인해보자.

분명 이동하려고 하는 채널 N은 0보다 크거나 같고, 500,000번보다 작거나 같은 것은 사실이다.

그러나, 문제의 두 번째 단락을 확인해보면 다음과 같은 문구가 있다.

 

채널은 무한대 만큼 있다.

 

채널은 사실 무한대 만큼 존재한다!

즉, 500,000번 채널로 가고 싶지만 숫자버튼 3, 4, 5가 고장났다고 가정했을 때,

가장 빠르게 해당 채널로 가는 방법은 299,999번에서 +를 200,001번 누르는 것이 아닌,

600,000번에서 -를 100,000번 누르는 방법 또한 존재한다는 의미가 된다.

 

이와 같은 이유로, 최대 1,000,000번 채널까지도 올라가야 할 수 있는 경우의 수가 존재하므로

반드시 for문은 1,000,000번까지 돌려야 한다.

 

for num in range(1000001) :

    num = str(num)
    for i in range(len(num)) :
        if int(num[i]) in broken :
            break

        elif i == len(num) - 1 :
            result = min(result, len(num) + abs(n - int(num))) # num 채널을 누르는데 든 횟수와 +- 를 누르는데 든 횟수

print(result)

 

이후엔 0번부터 시작하여 원하는 채널까지 +, -를 눌러 가는 방법,

1번부터 시작하여 원하는 채널까지 +, -를 눌러 가는 방법,

2번부터 시작하여 원하는 채널까지 +, -를 눌러 가는 방법,

3번부터 시작하여...

 

하는 방식으로 1,000,000번 부터 시작하여 원하는 채널까지 가는 방법을 전부 브루트포스 알고리즘으로 돌려본다!

 

그러나, 예를 들어 2번부터 시작하여 해당 채널까지 가보고싶지만

만약 고장난 버튼에 2번이 있다면 2번 채널에서 가는 방법은 아예 폐기한다.

 

만약 고장난 버튼이 없는 채널임이 확인된다면,

N(원하는 채널) - 현재 확인하는 채널 = + 혹은 -만 눌러 가는 횟수

에 현재 확인하는 채널까지 가기 위해 그 채널을 누르는 횟수 = 현재 확인하는 채널의 글자수

 

즉, (+ 혹은 -만 눌러 가는 횟수) + (현재 확인하는 채널의 글자수) 를 구한 뒤

기존에 구해놨던 result (그냥 100번 채널에서 +, -만 눌러 가는 횟수) 와 비교하여

더 버튼을 적게 누르는 방법을 result에 씌우는 것이다.

 

이걸 0번부터 1,000,000번까지 돌린다면...

결국 result엔 원하는 채널까지 갈 수 있는 최소한의 버튼 클릭 횟수가 저장될 것이다!

 

---

 

최대한 쉽고 간단하게 풀어 써보고자 해설을 작성했는데,

그럼에도 역시 코딩 테스트 문제 풀이를 가독성 좋게 작성하기란 쉽지 않은 것 같다.

문제 답습 및 복습과 정리에 중점을 둔다는 생각으로, 앞으로도 하나씩 문제풀이를 더 작성해보려고 한다.