[백준] 1107번 : 리모컨 (🥇골드 5) (Python)

문제 바로 가기

1107번: 리모컨

 

---

풀이

• 사용 언어 : Python
• 풀이한 날짜 : 2024-01-10

 

target = int(input())
btn_errors = int(input())

if btn_errors:
    error_btn_lst = list(map(int, input().split()))
else:
    error_btn_lst = []

target_lst = list(str(target))
min_cnt = abs(100 - target)


def check_valid(n):
    lst = map(int, list(str(n)))
    for elem in lst:
        if elem in error_btn_lst:
            return False
    return True


for i in range(1000001):
    if not check_valid(i):
        continue
    min_cnt = min(min_cnt, abs(i - target) + len(str(i)))

print(min_cnt)

모든 경우의 수를 탐색하는 브루트포스 방식을 이용하여 해결하였다. 

 

 

문제 접근 과정 및 느낀점

이 문제는 처음에 다른 방식으로 접근하였다.

이동해야 하는 목표 채널의 앞자리부터 순차적으로 확인하면서 해당 자리수에 해당하는 리모컨 버튼이 망가졌는지 확인한 후, 만일 망가졌다면 그 숫자의 바로 다음 숫자와 이전 숫자를 확인한다. 예를 들어 목표 채널이 8로 시작하는데, 만일 리모컨에서 버튼 8이 망가져있다면, 7과 9도 버튼이 멀쩡한지 확인한다. 이런 방식으로 목표 채널과 가장 가까운, 안 망가진 버튼으로 이동할 수 있는 소위 '근사 채널'을 찾는다.

 

이런 방식으로 풀었더니 대부분의 케이스에선 올바른 답을 출력했지만, 특정 케이스(ex. 80000(공식 테이스케이스 7번))에는 오답이 나왔다. 백준 질문 게시판에 올라온 반례들도 전부 올바르게 돌아가던데.. 말이다. (ㅜㅜ)

# 그냥 두기엔 너무 아까워서 올리는 기존의 풀이 방식으로 작성한 코드
# ❌ 올바른 코드 아님 (일부 테스트케이스 안 돌아감)

import sys

target = int(input())
btn_errors = int(input())
error_btn_lst = list(map(int, input().split()))

near_targets_lst = []
nominated_nums = [100]

# 1st > 변수 초기 세팅
# target 숫자의 각 자리를 탐색하기 위해 리스트화
target_lst = list(str(target))

# 버튼의 고장 여부를 딕셔너리로 정리
btn_lst = {}
for i in range(10):
    btn_lst[i] = False if i in error_btn_lst else True


##### 필요한 함수 선언 #####
def near_available_num_search(n):
    temp = []

    for i in range(1, 9):
        flag_right = False

        if btn_lst[(n + i) % 10]:
            temp.append((n + i) % 10)
            flag_right = True

        if flag_right:
            break

    for i in range(1, 9):
        flag_left = False

        if btn_lst[(n - i) % 10]:
            temp.append((n - i) % 10)
            flag_left = True

        if flag_left:
            break

    near_targets_lst.append(temp)
##### ------------ #####


# 2nd > 후보군 수 만들기(1) - 각 자리 탐색
for elem in target_lst:
    # elem의 버튼 고장 여부 판단
    num = int(elem)
    if btn_lst[int(num)]:
        near_targets_lst.append([num])
    else:
        near_available_num_search(num)


# 3rd > 후보군 수 만들기(2) - 순열 조합
nominated_num = []


def make_nominated_nums(curr_idx):
    if curr_idx == len(target_lst):
        nominated_nums.append(int(''.join(map(str, nominated_num))))
        # print(nominated_num)
        return

    for elem in near_targets_lst[curr_idx]:
        nominated_num.append(elem)
        make_nominated_nums(curr_idx + 1)
        nominated_num.pop()


make_nominated_nums(0)


# 4th > 후보군에서 장답 찾고 최소 버튼 클릭 횟수 구하기
min_cnt = sys.maxsize

for idx, elem in enumerate(nominated_nums):
    if idx == 0:
        min_cnt = min(min_cnt, abs(elem - target))
    else:
        min_cnt = min(min_cnt, abs(elem - target) + len(str(elem)))

print(min_cnt)

 

 

그래서 결국 이 방식대로는 내 힘으로 문제를 해결할 수가 없다고 판단하였고 (이미 4시간 이상 소모), 나와 비슷한 방식으로 접근했으나 비슷한 문제로 인해 다른 방식으로 문제를 해결한 다른 사람들의 풀이를 참고하면서 브루트포스 방식으로 이 문제를 다시 풀었다.

 

사실 이 방식은 시간 복잡도가 너무 높다고 생각하여 아예 배제하고 생각했었는데, 그게 실수였던 것 같다. 괜히 브루트포스 방식이 존재하는게 아닌데 말이다. 다음부터는 어떤 문제의 알고리즘을 생각할 때 모든 경우를 탐색해서 해결하는 방법을 반드시 고려해봐야겠다.