문제
수빈이는 TV를 보고 있다. 수빈이는 채널을 돌리려고 했지만, 버튼을 너무 세게 누르는 바람에, 일부 숫자 버튼이 고장났다.
리모컨에는 버튼이 0부터 9까지 숫자, +와 -가 있다. +를 누르면 현재 보고있는 채널에서 +1된 채널로 이동하고, -를 누르면 -1된 채널로 이동한다. 채널 0에서 -를 누른 경우에는 채널이 변하지 않고, 채널은 무한대 만큼 있다.
수빈이가 지금 이동하려고 하는 채널은 N이다. 어떤 버튼이 고장났는지 주어졌을 때, 채널 N으로 이동하기 위해서 버튼을 최소 몇 번 눌러야하는지 구하는 프로그램을 작성하시오.
수빈이가 지금 보고 있는 채널은 100번이다.
문제 정리
- 현 채널은 100
- 리모컨 버튼은 0~9, +, -
- 채널은 무한대
- N채널로 이동하기위해 눌러야하는 버튼을 구하여라
기본적으로는 두 단계로 이루어지면 된다.
1. N과 최대한 비슷한 숫자로 이동
2. 이후 남은 채널에 대해 +와 -로 이동
이후 조건과 예외케이스를 추가하면 된다.
문제 풀이
# N과 최대한 비슷한 숫자로 이동
# +와 - 를 섞어서 이동
n = int(input())
error_button_num = int(input())
if error_button_num == 0: # 예외 케이스1. 고장난 버튼이 없는 경우
error_buttons = []
else: error_buttons = list(input().split())
# 남은 버튼에서 최대한 비슷한 버튼으로 이동
# n값하고 차이가 나지 않는 것으로 이동해야함.
# 최소한의 차이를 구하고 최소한의 차이인 경우의 current값을 반환하면 된다.
# error_buttons : 고장난 버튼들의 종류(str list)
# n : 목표 숫자
# current : 고장나지 않은 버튼으로 만들 수 있는 채널
# close_num : current들 중 목표숫자와 가장 가까워지는 수
# length : close_num을 만들고자 하는 자릿수(1~len(N)+1)
def switch_channel_by_button(error_buttons, n, min_num, current, close_num, length):
if len(current) == length:
return abs(n-int(current)), current
for i in range(10):
si = str(i)
if si not in error_buttons:
temp_min, temp_current = switch_channel_by_button(error_buttons, n, min_num, current+si, close_num, length)
min_num = min(temp_min, min_num)
if min_num == temp_min:
close_num = temp_current
return min_num, close_num
# 채널을 +,-로만 바꾸었을때 결과
min_pm = 0
if n>=100: # 예외 케이스2 : 버튼을 사용해 이동하는 것보다 +,-로 이동하는 것이 더 빠른 경우
min_pm = n-100
else:
min_pm = 100-n
if error_button_num == 10: # 예외 케이스3 : 버튼10개 다 고장난 경우
print(min_pm)
else:
min_num = float('inf')
for i in range(1, len(str(n))+2): # 예외 케이스4 : N의 자릿수가 아닌 보다 작거나 보다 큰 자릿수의 이동이 더 빠른경우
temp_min_num, temp_close_num = switch_channel_by_button(error_buttons, n, float('inf'), '', '', i)
if min_num==temp_min_num: # 보다 작은 자릿수에서 최소값이 나오는 경우 그대로 유지
pass
if min_num > temp_min_num:
min_num = temp_min_num
close_num = temp_close_num
length = len(close_num)
close_num = int(close_num)
# abs(close_num-n) : 목표채널과 가장 비슷한 채널 - 목표채널 -> +,-를 몇 번 눌어야 하는지
# length : 고장난 것을 제외한 채널이동을 위해 0~9까지의 눌러야하는 버튼의 수
# min_pm : 0~9를 누르지 않고 +,-를 이용해 채널을 이동하는 경우 몇 번 누르는지
print(min(abs(close_num-n)+length,min_pm))풀이 후기
기본적인 로직에서 좀 더 다양한 예외를 포용할 수 있는 코드를 작성함이 어려웠다. 애초에 기본 로직 자체가 틀렸었다
처음에는 N번 채널과 가장 비슷한 채널로 이동해야하는 경우를 N번 채널의 자릿수로 고정시키고 했었다.
ex) N이 1555이고 고장난 버튼이 [0, 1, 9]라면
N의 자릿수가 4이기에 2222가 최선인줄 알았지만 888로 이동하는 것이 최선이다.
왜냐! 2222-1555 = 667이고 1555-888 = 667 로 같지만
888을 누르게 되면 8을 세 번 누르고 2222를 누르면 2를 네 번 누르기에
2222-1555+4(자릿수)=671이고 1555-888+3(자릿수)=670이다.
때문에 보다 작은 자릿수에 예외처리를 했으나 이도 완벽하지 않았었다.
ex) N이 9999이고 고장난 버튼이 [9]라면
8888로 이동하는 것보다 10000으로 이동하는 것이 효율적임을 알지만 자릿수 탐색을 1~N자릿수로 설정했기에 8888이 나오게 됐다. 때문에 1~N자릿수+1로 설정하여 이를 해결하였다.
기본적으로 예외처리할 것이 많아 정답률이 25%도 안나오는 것 같다. 당장 기본 테스트 케이스만 하더라도 한번에 전부 통과하지 못했으니 말이다. 이를 제외한 기본 풀이 자체는 나름 할만 했던 것 같다.
