[BOJ 백준] 1107 : 리모컨 - python

SUN·2022년 12월 3일
0

algorithm

목록 보기
28/30

요즘 바빠서 포스팅을 못했다ㅠ 한동안 좀 더 바쁠 거 같은데.. 그래도 시간날 때 틈틈이 포스팅해야겠다!
오랜만에 풀어볼 문제는 리모컨이다.

문제

풀이과정

이 문제는 몇달전에 풀려고 했는데 방법을 전혀 모르겠어서 포기했던 문제다.
근데 이번에 다시 보고 20분 정도 고민하니까 푸는 방법이 떠올랐다.
알고리즘을 조금은 잘하게 된 거 같아서 기쁘다.

내가 생각한 방법은 아래와 같다.
타겟 채널로 갈 수 있는 방법은 두가지 밖에 없다.

  1. 숫자 버튼을 사용해 이동할 수 있는 채널중에 타겟과 가장 가까운 채널로 이동한 후에
    그 채널에서 +나 -를 이용해 타겟 채널로 이동한다.
  2. 숫자 버튼을 쓰지 않고 +나 -만으로 타겟 채널로 이동한다.

그래서 이 두 방법의 이동 횟수 중에 최솟값을 구하면 정답이 된다.
그렇다면 어떻게 각 방법의 이동횟수를 구할 수 있을까?
나는 이렇게 생각했다.

타겟 채널에서 채널을 하나씩 증가, 감소 시켜가면서 그 채널로 이동할 수 있는 지 확인한다.
그리고 처음으로 이동할 수 있는 채널이 나오면 그 채널이 바로
숫자버튼을 눌러서 갈 수 있는 타겟과 가장 가까운 채널일 것이다.

그리고 그 채널에서 타겟 채널까지의 거리를 계산하면 최소 이동 횟수를 구할 수 있다.
왜냐면 그 채널에서 타겟 채널까지의 거리만큼 +나 -를 눌러야 하기 때문이다.
이제 이걸 숫자 버튼을 사용하지 않고 +나 -만으로 타겟 채널에 가는 이동 횟수랑 비교해서
더 작은 이동횟수가 정답이 될 것이다.

이걸 토대로 알고리즘을 짰다.

실패코드

# 이 채널로 이동 가능한 지 확인하기
def is_possible_move_to(channel):
    global broken_numbers
	
    # 채널에 들어가는 숫자들을 모두 돌면서 부서진 숫자가 있는 지 확인하기
    while True:
        remainder = channel % 10
        channel = channel // 10
		
        # 부서진 숫자가 있으면 이 채널로 이동 불가
        if remainder in broken_numbers:
            return False
		
        # 모두 다 돌았으면 break
        if channel == 0:
            break

    return True

# 더 작은 횟수 반환
def find_min_move_count(curr_channel, min_move_count):
    global target_channel
	
    # curr_channel로 가기위해 움직여야하는 최소 횟수
    # == 현재 채널의 자릿수 + 현재 채널에서 타겟 채널까지 거리
    # 왜냐면 현재 채널 자릿수만큼 숫자 버튼을 눌러서 이동해야하고 
    # 현재 채널에서 타겟 채널까지 거리만큼 +나 -를 눌러야하기 때문에
    move_count = abs(target_channel - curr_channel) + len(str(curr_channel))
    if move_count < min_move_count:
        min_move_count = move_count
    return min_move_count


target_channel = int(input())
number_of_broken_buttons = int(input())

broken_numbers = []
if number_of_broken_buttons:
    broken_numbers = [int(number) for number in input().split()]

up_channel = target_channel
down_channel = target_channel

# 처음 최소 횟수는 현재 채널인 100번에서 숫자 버튼 안누르고 +나 -만 해서 갈 수 있는 횟수로 초기화
min_move_count = abs(target_channel - 100)

# 타겟 채널로 가는데 필요한 버튼 중에 부서진 버튼이 없어서 타겟채널로 바로 이동할 수 있으면
if is_possible_move_to(target_channel):
	# 최소 이동 횟수 계산
    min_move_count = find_min_move_count(target_channel, min_move_count)
# 아니라면
else:
	# 이동할 수 있는 채널을 발견할 때 까지 반복
    while True:
    	# 채널을 +1해본다
        up_channel += 1
        # 채널을 -1해본다 
        down_channel -= 1
		
        # +1한 채널로 이동할 수 있으면
        if is_possible_move_to(up_channel):
        	# 기존 최소 이동 횟수와 비교해서 더 작은 이동 횟수를 찾고 멈춤
            min_move_count = find_min_move_count(up_channel, min_move_count)
            break 
            
        # -1한 채널로 이동할 수 있으면
        if is_possible_move_to(down_channel):
        	# 기존 최소 이동 횟수와 비교해서 더 작은 이동 횟수를 찾고 멈춤
            min_move_count = find_min_move_count(up_channel, min_move_count) #여기
            break

print(min_move_count)

처음에 짰던 코드는 이거다.
맞을 거라고 생각했는데 틀려서 대체 뭐가 문제지?하고 시간을 낭비했다.
하나씩 고치면서 다시 제출하면서 문제를 고쳐가면서 틀린 이유를 깨달았다.
이 코드가 틀린 이유는 아래와 같다.

가장 큰 요인은 오타였다.
주석으로 '여기'라고 달아놓은 부분에 up_channel이 아니라
down_channel인데 복사 붙여넣기 하다가 바꾸는 걸 깜빡했다.
이런 사소한 걸 틀리다니.. 꼼꼼히 봐야겠다고 생각했다.

두번 째는 +1한 채널로 이동할 수 있으면서 -1한 채널로도 이동할 수 있는 경우가 있기 때문에
하나만 체크하고 break를 하면 안된다. 두 경우 모두 본 다음에 break를 해야한다.

세번 째는 이동할 수 있는 채널을 발견할 때 까지 반복하는 반복문의 탈출 조건이 부족했다.

숫자버튼으로 채널을 변경한다음에 +나 -를 하는 경우의 이동 횟수가
숫자버튼을 아예 누르지 않고 +나 -만 해서 갈 수 있는 이동 횟수보다 커지는 순간이 왔을 때는
더이상 반복문을 계속할 필요가 없다.

왜냐하면 반복문을 진행할수록 타겟넘버에서 더 멀어지기 때문에 이동 횟수는 더 커질 수 밖에 없기 때문이다.
이걸 간과해서 시간초과가 났었다.

네번 째는 down_channel이 마이너스일 경우에 처리가 필요하다.
-로는 이동할 수 없는데 이 코드로 하면 이동할 수 있다고 나올 수 있어서 처리를 해줘야한다.

이 부분을 고치니까 성공할 수 있었다ㅎㅎ

성공 코드


# 이 채널로 이동 가능한 지 확인하기
def is_possible_move_to(channel):
    global broken_numbers
	
    # 채널에 들어가는 숫자들을 모두 돌면서 부서진 숫자가 있는 지 확인하기
    while True:
        remainder = channel % 10
        channel = channel // 10
		
        # 부서진 숫자가 하나라도 있으면 이 채널로 이동 불가
        if remainder in broken_numbers:
            return False
		
        # 모두 다 돌았으면 break
        if channel <= 0:
            break

    return True


# 이 채널로 가기 위한 최소 이동 횟수 계산
def calculate_move_count(curr_channel):
    global target_channel
	
    # curr_channel로 가기위해 움직여야하는 최소 횟수
    # == 현재 채널의 자릿수 + 현재 채널에서 타겟 채널까지 거리
    # 왜냐면 현재 채널 자릿수만큼 숫자 버튼을 눌러서 이동해야하고 
    # 현재 채널에서 타겟 채널까지 거리만큼 +나 -를 눌러야하기 때문에
    return len(str(curr_channel)) + abs(target_channel - curr_channel)


target_channel = int(input())
number_of_broken_buttons = int(input())

broken_numbers = []
if number_of_broken_buttons:
    broken_numbers = [int(number) for number in input().split()]

# 타겟 채널에서 +1씩 해보면서 숫자 버튼으로 갈 수 있는 타겟 채널과 가장 가까운 채널을 찾기위해
up_channel = target_channel
# 타겟 채널에서 -1씩 해보면서 숫자 버튼으로 갈 수 있는 타겟 채널과 가장 가까운 채널을 찾기위해
down_channel = target_channel

# 초기 이동 횟수는 현재 채널인 100번에서 숫자 버튼 안누르고 +나 -만 해서 갈 수 있는 횟수로 정의
init_count = abs(target_channel - 100)
# 최소 이동 거리는 일단 초기 이동 횟수로 초기화
min_move_count = init_count

# 타겟 채널로 가는데 필요한 버튼 중에 부서진 버튼이 없어서 타겟채널로 바로 이동할 수 있으면
if is_possible_move_to(target_channel):
    min_move_count = min(calculate_move_count(target_channel), min_move_count)

else:
	# 이동할 수 있는 채널을 발견할 때 까지 반복
    while True:
    	# 타겟 채널에서 +1씩 해본다.
        up_channel += 1
        # 타겟 채널에서 -1씩 해본다
        down_channel -= 1

        found = False
		
        # +1한 채널으로 이동한 다음에 타겟 채널로 이동하는 경우의 이동 횟수를 구한다.
        up_channel_count = calculate_move_count(up_channel)
        # -1한 채널으로 이동한 다음에 타겟 채널로 이동하는 경우의 이동 횟수를 구한다.
        down_channel_count = calculate_move_count(down_channel)
		
        # +1한 채널으로 이동한 다음에 타겟 채널로 이동하는 경우의 이동 횟수가
        # 숫자버튼을 아예 누르지 않고 +나 -만 해서 갈 수 있는 이동 횟수보다 
        # 커지는 순간이 왔을 때는 break해야 시간 초과가 안난다.
        # 반복문을 진행할수록 타겟채널에서 더 멀어지기 때문에 이동 횟수는 더 커질 수 밖에 없기 때문에
        if up_channel_count > init_count:
            break
            
		# +1한 채널로 이동할 수 있으면
        if is_possible_move_to(up_channel):
        	# 기존 최소 이동 횟수와 비교해서 더 작은 이동 횟수를 찾는다.
            min_move_count = min(up_channel_count, min_move_count)
            found = True
		
        # -1한 채널로 이동할 수 있으면 + down_channel이 마이너스가 아니면
        if down_channel >= 0 and is_possible_move_to(down_channel):
        	# 기존 최소 이동 횟수와 비교해서 더 작은 이동 횟수를 찾는다.
            min_move_count = min(down_channel_count, min_move_count)
            found = True
		
        # 만약 현재 +1한 채널로 이동할 수 있거나 -1한 채널로 이동할 수 있었으면
        # 최소 이동횟수를 구했다는 뜻이기 때문에 멈춤
        if found:	
            break

print(min_move_count)

성공 코드 - 주석 없는 버전

def is_possible_move_to(channel):
    global broken_numbers

    while True:
        remainder = channel % 10
        channel = channel // 10

        if remainder in broken_numbers:
            return False

        if channel <= 0:
            break

    return True


def calculate_move_count(curr_channel):
    global target_channel

    return abs(target_channel - curr_channel) + len(str(curr_channel))


target_channel = int(input())
number_of_broken_buttons = int(input())

broken_numbers = []
if number_of_broken_buttons:
    broken_numbers = [int(number) for number in input().split()]

up_channel = target_channel
down_channel = target_channel

init_count = abs(target_channel - 100)
min_move_count = init_count

if is_possible_move_to(target_channel):
    min_move_count = min(calculate_move_count(target_channel), min_move_count)

else:
    while True:
        up_channel += 1
        down_channel -= 1

        found = False

        up_channel_count = calculate_move_count(up_channel)
        down_channel_count = calculate_move_count(down_channel)

        if up_channel_count > init_count:
            break

        if is_possible_move_to(up_channel):
            min_move_count = min(up_channel_count, min_move_count)
            found = True

        if down_channel >= 0 and is_possible_move_to(down_channel):
            min_move_count = min(down_channel_count, min_move_count)
            found = True

        if found:
            break

print(min_move_count)

이렇게 해서 드디어 정답..ㅠㅠ
조건을 따질 게 많아서 힘들었다.

다른 사람의 코드

import sys

n = int(sys.stdin.readline())
m = int(sys.stdin.readline())
broken = list(map(str, sys.stdin.readline().split()))
cnt = abs(100 - n) # 리모컨을 눌러야하는 최대 개수

# 반복문을 통해 이동해야하는 채널로 가기 위한 방법을 확인
for i in range(1000001):

    # 반복문을 통해 채널로 이동하기 위해 눌러야 하는 번호가 고장이 났는지 확인
    for j in str(i):
        if j in broken:
            break

    # 채널로 이동 가능하다면 원래 cnt와 채널을 누른 개수와 +/- 를 누른 개수를 cnt에 담는다.
    else:
        cnt = min(cnt, len(str(i)) + abs(i - n))

print(cnt)

이렇게 그냥 1부터 100만정도 까지의 채널을 모두 돌면서 이동이 가능하면 최소 이동 횟수를 갱신하는,
말그대로 모든 경우를 다 따져보는 식의 풀이가 많았다.
100만인 이유는 타겟 채널은 50만인데 전체 채널은 무한이니까 적당히 2배로 해서 커버한 것 같다.
충격적이다 나의 길디 긴 코드에 비해... 너무 짧다.......
이렇게 간단하게 풀수 있다니....

그래도 내 풀이는 타겟 채널부터 시작해서 이동할 수 있는 채널을 발견하면 바로 멈추는 반면
이런 풀이는 어떤 경우에도 100만개를 전부 돌아야 하기 때문에 속도 측면에선 내 풀이가 조금 더 효율적일 것 같긴하다.

실제로 아래는 내 코드, 위에는 이 코드의 결과인데 내 코드가 비교적 빠른 것을 볼 수 있다.

하지만 가독성은 이 풀이가 훨씬 뛰어나다. 그리고 구현이 정말 간단하다.

다음에는 이런식으로 범위가 100만 정도로 그렇게 넓지 않다면 완전탐색으로 푸는 방법도 꼭 생각해야겠다.

profile
개발자

0개의 댓글