| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 256 MB | 104942 | 25884 | 18210 | 23.189% |
문제
수빈이는 TV를 보고 있다. 수빈이는 채널을 돌리려고 했지만, 버튼을 너무 세게 누르는 바람에, 일부 숫자 버튼이 고장났다.
리모컨에는 버튼이 0부터 9까지 숫자, +와 -가 있다. +를 누르면 현재 보고있는 채널에서 +1된 채널로 이동하고, -를 누르면 -1된 채널로 이동한다. 채널 0에서 -를 누른 경우에는 채널이 변하지 않고, 채널은 무한대 만큼 있다.
수빈이가 지금 이동하려고 하는 채널은 N이다. 어떤 버튼이 고장났는지 주어졌을 때, 채널 N으로 이동하기 위해서 버튼을 최소 몇 번 눌러야하는지 구하는 프로그램을 작성하시오.
수빈이가 지금 보고 있는 채널은 100번이다.
입력
첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼이 주어지며, 같은 버튼이 여러 번 주어지는 경우는 없다.
출력
첫째 줄에 채널 N으로 이동하기 위해 버튼을 최소 몇 번 눌러야 하는지를 출력한다.
답안
import math
import sys
target = sys.stdin.readline().strip()
len_broken_buttons = int(sys.stdin.readline())
available_buttons = []
if (len_broken_buttons == 0):
available_buttons = [str(i) for i in range(10)]
else:
available_buttons = sorted(list(set([str(i) for i in range(10)]) -
set(sys.stdin.readline().split())))
def _add_digit(candidate_buttons, candidate_digits):
result = []
if len(candidate_buttons) == 0:
result = candidate_digits
for i in range(len(candidate_buttons)):
for j in range(len(candidate_digits)):
result.append(candidate_buttons[i] + candidate_digits[j])
return result
def _get_candidate_buttons(target, available_buttons):
candidate_buttons = []
for i in range(len(target)):
candidate_buttons = _add_digit(candidate_buttons, available_buttons)
i = 0
for i, candidate_button in enumerate(candidate_buttons):
if candidate_button >= target:
break
if (len(candidate_buttons) == 0):
return []
return [candidate_buttons[(i-1) % len(candidate_buttons)], candidate_buttons[i]]
def get_number_of_button_presses(target, candidate):
return len(str(int(candidate))) + abs(int(target) - int(candidate))
def get_answer_from_digit_number_n(target, available_buttons):
candidates = _get_candidate_buttons(target, available_buttons)
return min(list(map(lambda x: get_number_of_button_presses(target, x), candidates)))
def get_answer_from_digit_number_n_minus_1(target, available_buttons):
if len(available_buttons) == 0:
return math.inf
elif len(available_buttons) == 1:
if available_buttons[0] == '0':
return math.inf
if len(target) == 1:
return math.inf
candidate = max(available_buttons) * (len(target) - 1)
return get_number_of_button_presses(target, candidate)
def get_answer_from_digit_number_n_plus_1(target, available_buttons):
if len(available_buttons) == 0:
return math.inf
elif len(available_buttons) == 1:
if available_buttons[0] == '0':
return math.inf
candidate = available_buttons[0] * (len(target) + 1)
return get_number_of_button_presses(target, candidate)
first_digit = min(filter(lambda x: x != '0', available_buttons))
rest_digit = min(available_buttons)
candidate = first_digit + rest_digit * len(target)
return get_number_of_button_presses(target, candidate)
def solve(target, available_buttons):
if (target == '100'):
print('0')
return
if len(available_buttons) == 0:
print(abs(int(target) - 100))
return
print(min(get_answer_from_digit_number_n(target, available_buttons),
get_answer_from_digit_number_n_minus_1(
target, available_buttons),
get_answer_from_digit_number_n_plus_1(target, available_buttons),
abs(int(target) - 100)))
solve(target, available_buttons)풀이
버튼을 최소한으로 누르기 위해서는, 0-9번의 버튼을 눌러 목표 채널과 가장 근접한 채널로 가는 것이 중요하다. 그렇게 해야 + 버튼 혹은 - 버튼을 누르는 횟수를 최소한으로 할 수 있기 때문이다.
이동하려는 채널은 0과 200,000 사이의 범위이다. 즉, 이동하려는 채널로 가기 위해 가장 근접한 채널로 간다고 하더라도 그 채널의 자리수는 6자리를 넘지 않는다.
하나의 자리에 최대 0-9 10개의 숫자가 들어갈 수 있으므로, 6자리 모든 채널의 경우의 수를 살펴본다고 하더라도 모든 경우의 수는 10^6개이다.
문제의 시간 제한인 2초 안에 10^6개의 경우의 수는 충분히 살펴볼 수 있을 것으로 생각되므로, 모든 경우의 수를 살펴보아도 될 것 같다.
하지만, n자리의 목표 채널이 주어졌을 때 n자리 채널의 모든 경우의 수를 살펴본다고 하더라도, 그밖의 예외 상황들을 고려해야 한다.
예를 들어 다음과 같은 경우이다.
- 목표 채널: 1000
- 고장나지 않은 숫자 버튼: 9
이 경우, 가장 근접한 채널로 가기 위해 4자리 숫자 9999를 만드는 것보다 3자리 숫자 999를 만든 뒤 + 버튼을 눌러 1000으로 가는 것이 더 빠르다.
이와 비슷하게, 다음과 같은 경우에
- 목표 채널: 999
- 고장나지 않은 숫자 버튼: 1, 0
가장 근접한 채널로 가기 위해 3자리 숫자 111을 만드는 것보다, 4자리 숫자 1000을 만든 뒤 - 버튼을 눌러 999로 가는 것이 더 빠르다.
이와 같이, n자리의 목표 채널이 주어졌을 때 n자리뿐만 아니라 n-1자리, n+1자리 숫자도 고려해야 하는 것이다.
이때, n-1자리의 숫자의 경우에는 목표 채널과 가장 가까운 숫자, 즉 만들 수 있는 n-1자리 숫자들 중에서 가장 큰 수만 고려하면 된다. + 버튼을 누르는 횟수를 최소로 만드는 경우이기 때문이다.
또한, n+1자리의 숫자의 경우에는 목표 채널과 가장 가까운 숫자, 즉 만들 수 있는 n+1자리 숫자들 중 가장 작은 수만 고려하면 된다. - 버튼을 누르는 횟수를 최소로 만드는 경우이기 때문이다.
정리하면, 고장나지 않은 버튼들을 이용해서
- n자리 숫자 모든 경우의 수,
- n-1자리 숫자 중 가장 큰 수,
- n+1자리 숫자 중 가장 작은 수
를 모두 찾아본 뒤, 그중 버튼을 누르는 횟수가 가장 적은 경우를 고르면 된다.
사실 여기까지 구현을 마치고 채점을 시도했는데, 틀렸습니다가 떴다.
확인하지 않은 경우의 수가 있었다는 것이다.
고민하다가 질문게시판을 통해 확인하지 않은 어떤 경우의 수가 있었는지 확인해봤는데,
100에 근접한 숫자들이 목표 채널로 제시되었을 때, 100에 근접한 숫자들로 이동한 뒤 + 혹은 - 버튼을 누르는 것보다 아예 처음부터 + 혹은 - 버튼을 눌러 100번 채널로 이동하는 것이 더 적은 횟수로 버튼을 누를 수 있는 경우가 있었던 것이다.
즉, abs(목표채널 - 100)과 위 횟수들을 비교해봐야 한다는 것이다.
이 4가지 경우를 모두 찾았다면 구현만 남았다.
구현이 복잡한 편이라, 여러 개의 함수로 분리하여 구현하였다.
def solve(target, available_buttons):
if (target == '100'):
print('0')
return
if len(available_buttons) == 0:
print(abs(int(target) - 100))
return
print(min(get_answer_from_digit_number_n(target, available_buttons),
get_answer_from_digit_number_n_minus_1(
target, available_buttons),
get_answer_from_digit_number_n_plus_1(target, available_buttons),
abs(int(target) - 100)))가장 중심적인 기능을 하는 함수 solve()이다.
목표 채널(target)이 100이어서 아무런 버튼을 누르지 않아도 되는 경우와, 사용 가능한 숫자 버튼이 없는 경우는 예외적인 경우로 처리해주었다.
이 경우들을 처리해주지 않으면 아래 함수 실행 도중에 오류가 뜨게 되므로 먼저 처리해줬다.
위에서 말한 것과 같이,
- n자리 숫자 모든 경우의 수,
- n-1자리 숫자 중 가장 큰 수,
- n+1자리 숫자 중 가장 작은 수
- 또는 - 버튼만을 누르는 경우의 수
4가지를 비교해 버튼을 누르는 횟수의 최솟값을 구한다.
def _add_digit(candidate_buttons, candidate_digits):
result = []
if len(candidate_buttons) == 0:
result = candidate_digits
for i in range(len(candidate_buttons)):
for j in range(len(candidate_digits)):
result.append(candidate_buttons[i] + candidate_digits[j])
return result
def _get_candidate_buttons(target, available_buttons):
candidate_buttons = []
for i in range(len(target)):
candidate_buttons = _add_digit(candidate_buttons, available_buttons)
i = 0
for i, candidate_button in enumerate(candidate_buttons):
if candidate_button >= target:
break
if (len(candidate_buttons) == 0):
return []
return [candidate_buttons[(i-1) % len(candidate_buttons)], candidate_buttons[i]]
...
def get_answer_from_digit_number_n(target, available_buttons):
candidates = _get_candidate_buttons(target, available_buttons)
return min(list(map(lambda x: get_number_of_button_presses(target, x), candidates)))n자리 숫자의 모든 경우의 수를 구하는 부분이다.
가능한 버튼들을 한 자리씩 더해 모든 경우의 수를 구한다.
지금 생각해보니 중복조합을 썼어도 괜찮았을 것 같다.
def get_answer_from_digit_number_n_minus_1(target, available_buttons):
if len(available_buttons) == 0:
return math.inf
elif len(available_buttons) == 1:
if available_buttons[0] == '0':
return math.inf
if len(target) == 1:
return math.inf
candidate = max(available_buttons) * (len(target) - 1)
return get_number_of_button_presses(target, candidate)n-1자리 경우의 수중 가장 큰 값을 구하는 부분이다.
오류가 발생하지 않도록 적절히 예외처리를 한 뒤, 사용 가능한 버튼들 중 가장 큰 수만을 n-1번 사용해 가장 큰 수를 만든다.
def get_answer_from_digit_number_n_plus_1(target, available_buttons):
if len(available_buttons) == 0:
return math.inf
elif len(available_buttons) == 1:
if available_buttons[0] == '0':
return math.inf
candidate = available_buttons[0] * (len(target) + 1)
return get_number_of_button_presses(target, candidate)
first_digit = min(filter(lambda x: x != '0', available_buttons))
rest_digit = min(available_buttons)
candidate = first_digit + rest_digit * len(target)
return get_number_of_button_presses(target, candidate)n+1자리 경우의 수도 n-1자리 경우의 수와 유사하게 가장 작은 값을 구한다.
위와 같이 적절히 예외처리하고, 사용 가능한 버튼들 중 가장 작은 수만을 n+1번 사용해 가장 큰 수를 만든다.
이때 주의할 점은 첫자리 숫자가 0이 아닌 가장 작은 수여야 한다.
이와 같이 모든 경우의 수를 확인하면 된다.
