요즘 바빠서 포스팅을 못했다ㅠ 한동안 좀 더 바쁠 거 같은데.. 그래도 시간날 때 틈틈이 포스팅해야겠다!
오랜만에 풀어볼 문제는 리모컨이다.
문제
풀이과정
이 문제는 몇달전에 풀려고 했는데 방법을 전혀 모르겠어서 포기했던 문제다.
근데 이번에 다시 보고 20분 정도 고민하니까 푸는 방법이 떠올랐다.
알고리즘을 조금은 잘하게 된 거 같아서 기쁘다.
내가 생각한 방법은 아래와 같다.
타겟 채널로 갈 수 있는 방법은 두가지 밖에 없다.
- 숫자 버튼을 사용해 이동할 수 있는 채널중에 타겟과 가장 가까운 채널로 이동한 후에
그 채널에서 +나 -를 이용해 타겟 채널로 이동한다. - 숫자 버튼을 쓰지 않고 +나 -만으로 타겟 채널로 이동한다.
그래서 이 두 방법의 이동 횟수 중에 최솟값을 구하면 정답이 된다.
그렇다면 어떻게 각 방법의 이동횟수를 구할 수 있을까?
나는 이렇게 생각했다.
타겟 채널에서 채널을 하나씩 증가, 감소 시켜가면서 그 채널로 이동할 수 있는 지 확인한다.
그리고 처음으로 이동할 수 있는 채널이 나오면 그 채널이 바로
숫자버튼을 눌러서 갈 수 있는 타겟과 가장 가까운 채널일 것이다.
그리고 그 채널에서 타겟 채널까지의 거리를 계산하면 최소 이동 횟수를 구할 수 있다.
왜냐면 그 채널에서 타겟 채널까지의 거리만큼 +나 -를 눌러야 하기 때문이다.
이제 이걸 숫자 버튼을 사용하지 않고 +나 -만으로 타겟 채널에 가는 이동 횟수랑 비교해서
더 작은 이동횟수가 정답이 될 것이다.
이걸 토대로 알고리즘을 짰다.
실패코드
# 이 채널로 이동 가능한 지 확인하기
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만 정도로 그렇게 넓지 않다면 완전탐색으로 푸는 방법도 꼭 생각해야겠다.
