[백준] 1107번: 리모콘 - 파이썬

🔈 문제

수빈이는 TV를 보고 있다. 수빈이는 채널을 돌리려고 했지만, 버튼을 너무 세게 누르는 바람에, 일부 숫자 버튼이 고장 났다.
리모컨에는 버튼이 0부터 9까지 숫자, +와 -가 있다. +를 누르면 현재 보고 있는 채널에서 +1된 채널로 이동하고, -를 누르면 -1된 채널로 이동한다. 채널 0에서 -를 누른 경우에는 채널이 변하지 않고, 채널은 무한대 만큼 있다.
수빈이가 지금 이동하려고 하는 채널은 N이다. 어떤 버튼이 고장났는지 주어졌을 때, 채널 N으로 이동하기 위해서 버튼을 최소 몇 번 눌러야하는지 구하는 프로그램을 작성하시오. 
수빈이가 지금 보고 있는 채널은 100번이다.

 

📝입력

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

 

📑출력

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

 

📚 문제 해석

처음에는 백트래킹나 DFS로 풀어야하나 잠깐 생각하였다가, 브루트포스로 풀 수도 있다는 것을 보았다. 그래서 어떤 식으로 브루트포스를 사용할지 고민해보았다. 0부터 500000번 채널(고장난 채널버튼은 제외)에 있을 때 n까지 가는 경우의 수를 전부!!! 저장하는 방법이 먼저 떠올랐다. 그래서 이 수를 만드는 방법을 생각하다가 백트래킹이 나온 것이었다. 이렇게 전부 계산하면 시간복잡도와 공간복잡도가 무시무시하다.

새로 생각해낸 방법은 n에서 +1을 하거나 -1을 하여 0부터 500000(고장난 채널버튼 제외)로 가는 것이다. 찾으면 그 값을 저장하고 출력하면 된다. 

섬세하게 체크해줘야 할 것이 있는데, 시작 위치는 100이라는 점과 고장난 버튼이 없을 경우 input 을 받지 않는 점이다. 

 

📖 풀이

candi 라는 리스트에 후보군 데이터를 집어 넣은 다음 최소값을 출력해주었다. 초기 리스트에는 현재 위치에서 오로지 + 또는 - 으로만 움직인 경우를 저장하였다. (abs(n-now))

만약 가고자 하는 곳이 100이라면 움직이지 않아도 되는 경우이기에 candi 리스트에 0을 넣는다.
만약 고장난 버튼이 없다면 바로 채널을 눌러서 움직이면 되니까 움직이고자하는 채널의 길이(누른버튼의 수)를 리스트에 넣는다.
만약 모든 숫자버튼이 고장났다면, 이동은 + 또는 - 로 밖에 하지 못하니 input만 받고 넘어간다. 이 경우는 처음에 추가해주었다.

위에 경우에 해당하지 않았다면, 브루트탐색 시작이닷!
사실 하나 더 예외처리가 남았다. 가고자 하는 채널이 한자리 일때 그리고 그 버튼이 고장나지 않았다면 1번만에 이동이 가능하기에 1을 리스트에 담아 주었다.
브루트탐색은 0부터 500000까지 i가 1씩 증가할 때 n-i 또는 n+i이 고장난 버튼을 누르지 않고 갈 수 있다면 그 경우 누른 버튼의 수를 리스트에 추가해주었다. n-i과 n+i 모두 하나씩 후보군에 넣을 수 있게 해주었다. 

 

💻 코드 1

# 첫번째 코드
import sys
input = sys.stdin.readline

n = int(input()) # 이동하고픈 채널
m = int(input()) # 고장난 버튼의 수
now = 100 # 현재 위치
candi = [abs(n-now)] # 오직 + 또는 - 만으로 움직인 경우 저장
if n == 100: # 이동하고자 하는 위치가 100이라면 가만히 있음, 0번 누름
    if m != 0:
        map(int,input().rstrip().split())
    candi.append(0)
elif m == 0: # 고장난 버튼이 없다면 바로 채널 누름, 채널의 길이번 만큼 누름
    candi.append(len(str(n)))
elif m == 10: # 전부 고장났다면 오직 +, -만으로 움직임, 7번째 줄에서 처리해줌
    map(int,input().rstrip().split())
else:
    breakup = set(map(int,input().split()))
    if len(str(n)) == 1 and n not in breakup: # 버튼 하나만으로 이동할 수 있음, 1번 누름
        candi.append(1)
        pass

    left = False # -버튼 누르는 경우 하나만 담기 위한 불리안
    right = False # + 버튼 누르는 경우 하나만 담기 위한 불리안
    for i in range(500001):
        plus = set(map(int,str(n+i))) # 플러스버튼 누름
        # 집합의 차집합을 사용하여 고장난 버튼을 눌렀는지 체크한다.
        # (현재 집합)과 (현재 집합 고장난 키)의 차집합의 차이가 없다면
        if len(plus) == len(plus-breakup): 
            candi.append(len(str(n+i))+i)  # 버튼 누른 횟수 캔디에 추가
            right = True # 이쪽 경로는 왔다는 것을 체크
        if 0 <= n-i: # 채널이 음수인 경우는 없음 
            minus = set(map(int,str(n-i)))
            if len(minus) == len(minus-breakup):
                candi.append(len(str(n-i))+i)
                left = True
        if left and right: # +키만으로, - 키만으로 누른 경우 모두 한번씩 추가해줬을 브루트포스멈춤
            break         

print(min(candi)) # 후보군의 최소값 출력

 

💻 코드 2

# 두번째 코드
import sys
input = sys.stdin.readline

n = int(input())
m = int(input())
now = 100
candi = [abs(n-now)]
if n == 100:
    if m != 0:
        map(int,input().rstrip().split())
    candi.append(0)
elif m == 0:
    candi.append(len(str(n)))
elif m == 10:
    map(int,input().rstrip().split())

else:
    breakup = set(map(int,input().split()))
    if len(str(n)) == 1 and n not in breakup:
        candi.append(1)
    else:
        left = False
        right = False
        for i in range(500001):
            plus = set(map(int,str(n+i)))
            if len(plus) == len(plus-breakup) and not right:
                candi.append(len(str(n+i))+i)
                right = True
            if 0 <= n-i and not left:
                minus = set(map(int,str(n-i)))
                if len(minus) == len(minus-breakup):
                    candi.append(len(str(n-i))+i)
                    left = True
            if left and right:
                break         

print(min(candi))

 

첫번째 코드와 두번째 코드의 차이는 첫번째 else 파트에 있다. 

만약 right 에 경우를 추가하였다면, left를 찾는 동안은 right 파트 연산을 하지 않고, 반대로 letf를 추가하였다면 right 를 찾는 동안 left 연산을 하지 않는 것이 두번째 코드이다.

공간복잡도의 차이가 꽤 난다.

아래가 첫번째 코드, 위에가 두번째 코드이다. right를 한번 넣었으면 더이상 right는 넣지 않고, left를 한번 넣었으면 더이상 left를 넣지 않기에 차이가 나는 것이다. 즉 두번째 코드의 후보군 리스트의 원소의 갯수는 최대 3개이다.

 

🔗 문제링크 : 리모컨

1107번: 리모컨

파이썬