알고리즘 스터디 - 백준 1107번 : 리모컨

문제 해석

수빈이가 고장난 버튼이 있는 리모컨으로 보고자 하는 채널로 가고 싶을 때 버튼을 눌러야 하는 횟수를 구하면 된다.

• 현재 수빈이의 채널은 100번이다.

어떤 알고리즘을 써야할까?

입력
1. 수빈이가 이동하려는 채널 N
2. 고장난 버튼의 개수 M
3. 고장난 버튼의 종류

입력 받고 나서 입력받은 숫자와 못쓰는 숫자가 있는지 체크
없으면 100과 가까운지와 입력받은 숫자 길이와 비교해서 작은 것
있으면 100과 가까운지 체크 및 입력받은 숫자에서 앞자리부터 가까운 수 사용

런타임 에러가 난 코드

N = int(input())
M = int(input())

# 사용가능한 버튼 구하기
number_button = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
repair = []
if M != 0:
    button = list(map(int, input().split()))
    repair.extend(button)

available_button = list(set(number_button) - set(repair))

# 100과의 거리
differ_with_100 = abs(N-100)

# 숫자를 리스트로 변환해 못쓰는 값이 있는지 체크
N_list = list(map(int, str(N)))
common_value = list(set(N_list) & set(repair))

# N이 100일 경우
if N == 100:
    print(0)
# 주어진 N에 대하여 사용가능한 버튼이 존재하는지
elif len(common_value) == 0:
    print(min(differ_with_100, len(str(N))))
# 주어진 N에 대하여 사용 못하는 버튼이 있는지
else:
    # 전체 횟수, 현재 숫자의 형태
    count, store = 0, ""

    # 앞자리부터 같은지 다른지 여부 체크
    front_same = True
    while N_list:
        check_num = "0" * (len(str(N)) - len(store))
        # 앞자리부터 지금까지 나온 숫자가 같은 경우
        if N_list[0] in available_button and front_same == True:
            count += 1
            store += str(N_list.pop(0))
        # 현재 숫자의 앞자리가 다른 경우
        # 현재 저장된 숫자에 아무 숫자도 없을 경우 가장 가까운 숫자 탐색 
        elif len(store) == 0:
            front_same = False
            differ, index = 10, 0
            for i in range(len(available_button)):
                if differ > abs(available_button[i] - N_list[0]): differ, index = abs(available_button[i] - N_list[0]), i
            
            count += 1
            store += str(available_button[index])
            print(available_button[index])
            N_list.pop(0)
        # 다를 때 타겟 숫자보다 작으면 그 다음 숫자는 무조건 큰 숫자 입력
        elif int(store + check_num) < int(N):
            front_same = False
            count += 1
            store += str(max(available_button))
            N_list.pop(0)
        # 다를 때 타겟 숫자보다 크면 그 다음 숫자는 무조건 작은 숫자 입력
        elif int(store + check_num) >= int(N):
            front_same = False
            count += 1
            store += str(min(available_button)) 
            N_list.pop(0)
    
    count += abs(int(store) - int(N))
    print(count)

• 이 경우 고려해야하는 경우의 수가 많아 런타임 에러가 난듯 하다 로컬에서 테스트케이스는 다 통과되었기는 했다.
• 구현 문제라고 생각을 했는데 구현이 아니고 다른 방식을 생각해보자.
• Class 3인데 너무 어려운 알고리즘을 생각하지는 않았겠고 한번 브루트 포스로 해보자.
• 갈 수 있는 채널이 50만인데 2~9까지의 숫자로 표현할 수 없는 경우 100만까지의 숫자도 가능한 경우라 최대 100만까지의 숫자를 돌아보면서 비교해보자.

브루트 포스니까 0~100만까지 돌면서 숫자 내 안되는 버튼이 있는지 체크
있다면 pass 없다면 n-100, n-현재 숫자 + len(현재 숫자)

알고리즘 코드

N = int(input())
M = int(input())

repair = []
if M != 0:
    button = list(map(int, input().split()))
    repair.extend(button)

count = abs(N-100)
for i in range(1000001):
    jump = False
    for j in list(str(i)):
        if int(j) in repair:
            jump = True
            break
    if jump:
        continue
    else:
        count = min(count, abs(N-i) + len(str(i)))

print(count)

• 정답은 맞췄으나 로컬에서 돌렸을 때 브루트 포스가 엄청 느린데 과연 이렇게 하는게 맞는지는 모르겠다.

문제 유형을 파악하기란 정말 어려운 것 같다. 항상 해석을 잘해보자. 이번에는 구체적인 시간복잡도를 계산함에 있어 부족한 부분이 있는 것 같다.