박민규

좋은 개발자가 되자

[Gold V] 리모컨 - 1107

문제 링크

성능 요약

메모리: 31256 KB, 시간: 1228 ms

분류

브루트포스 알고리즘

문제 설명

수빈이는 TV를 보고 있다. 수빈이는 채널을 돌리려고 했지만, 버튼을 너무 세게 누르는 바람에, 일부 숫자 버튼이 고장났다.

리모컨에는 버튼이 0부터 9까지 숫자, +와 -가 있다. +를 누르면 현재 보고있는 채널에서 +1된 채널로 이동하고, -를 누르면 -1된 채널로 이동한다. 채널 0에서 -를 누른 경우에는 채널이 변하지 않고, 채널은 무한대 만큼 있다.

수빈이가 지금 이동하려고 하는 채널은 N이다. 어떤 버튼이 고장났는지 주어졌을 때, 채널 N으로 이동하기 위해서 버튼을 최소 몇 번 눌러야하는지 구하는 프로그램을 작성하시오.

수빈이가 지금 보고 있는 채널은 100번이다.

입력

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

출력

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

코드

import sys

goal_num = int(sys.stdin.readline())
current_num = 100
broken_num = int(sys.stdin.readline())
broken_list = []
available_list = []
btn_list = [x for x in range(10)]

if broken_num != 0:
    broken_list = list(map(int, sys.stdin.readline().split()))

for broken_btn in broken_list:
    btn_list.remove(broken_btn)

def check_number(number, num_list=broken_list):
    number_str = str(number)
    for digit in number_str:
        if int(digit) in num_list:
            return True
    return False

# btn list에 사용 가능한 button 저장

# btn list에 있는 숫자를 조합해 goal_num과 가장 가까운 수를 만들어내고 그 차이 출력
# 사용 가능하지 않은 버튼이 들어가있는지를 확인
min = 1000002
target = 0
for i in range(0, 1000001):
    if ((check_number(i) == False) and (abs(goal_num - i) < min)):
        min = goal_num - i
        target = i

remote1 = len(str(target)) + abs(goal_num - target)
# 그 후 +또는 -만으로 움직이는 것과의 차이를 비교해 작은 수를 출력
remote2 = abs(goal_num - 100)

if len(broken_list) == 10 or remote2 < remote1:
    print(remote2)
else:
    print(remote1)

코드 리뷰

이번 문제는 브루트포스 알고리즘 유형으로, 리모컨의 일부 숫자 버튼이 고장나 있는 상황에 현재 채널에서 목표 채널까지 갈 수 있는 최소한의 버튼 클릭 횟수를 출력하는 문제다. 나는 check_number(number, num_list=broken_list)함수를 작성해 리모컨에서 고장나지 않은 버튼인지 체크하는 과정을 거치도록 하였다. 숫자를 적절히 입력해 이동하는 것 과 +/- 버튼만을 눌러 이동하는 방법 중 더 최소한의 값을 구하면 된다.

댓글남기기

참고