[골드 V] 1107번. 리모컨

 문제 

https://www.acmicpc.net/problem/1107

1107번: 리모컨

 사용 언어 

Python3

 풀이 과정 

이 문제는 처음에 경우를 너무 많이 나눠야 하는거 아닌가 고민됐는데 알고리즘 분류를 보니까 브루트 포스를 사용하면 됐다. 그런데 브루트 포스 문제 저번에 한 번 풀어봤지만 어떻게 구현해야 할지 감이 안와서 난 결국 product(중복조합)을 사용했다.

 

제출했더니 천천히 올라가길래 맞았나 했는데 96%에서 틀렸습니다가 떴다... 이럴수가

근데 절대 예외 케이스를 스스로 못찾을 것 같아서 질문 검색에 들어가봤고, 나처럼 96%에서 문제가 생기신 분의 댓글로 달아준 예외 케이스가 나한테도 해당되었다!!!

질문 검색 들어가니까 사람들이 다 리모컨 뿌시려다가 참고 마지막으로 질문한다... 티비도 안보는데 왜 리모컨으로 고생하는지 모르겠다 등... 예외 케이스 찾는 개발자들의 애원이 너무 웃겼다 ㅋ

 

문제는 고장난 버튼이 없을 때 바로 length를 출력하도록 했는데, 그러면 99나 101의 경우 100번에서 버튼 한 번으로 이동할 수 있지만 내 코드에서는 각각 2,  3이 출력된다. 

def main():
    channel_num = int(input())
    broken = int(input())
    length = len(str(channel_num))
    if broken == 0:
        print(length)
    else:
        ...

 

그래서 거기에도 100에서의 거리와 비교해서 min 값으로 설정해주니까 바로 맞았습니다!!

그런데 메모리랑 시간이 심각해서 ㅋㅋㅋㅋㅋ 브루트 포스 방식으로 푸는 게 시간과 공간이 훨씬 절약될 것 같아서 다른 사람 풀이로 다시 공부했다.

 

 제출 답안 

from itertools import product
from sys import stdin
input = stdin.readline

# 현재 100번에서 시작
# 먼저 제일 가까운 숫자를 찾아야 함
def main():
    channel_num = int(input())
    broken = int(input())
    length = len(str(channel_num))
    if broken == 0:
        print(min(length, abs(channel_num - 100)))
    else:
        # 일단 answer에 100번과의 차이를 저장
        answer = abs(channel_num - 100) if channel_num != 100 else 0

        broken_nums = set(input().split())
        nums = set(["1", "2", "3", "4", "5", "6", "7", "8", "9", "0"])
        normal_nums = nums - broken_nums

        # 가능한 조합 중 원하는 채널보다 하나 작은 개수, 같은 개수, 하나 많은 개수의 길이인 경우 구하기
        possible_nums = []
        if length == 1:
            for x in range(length, length + 2):
                possible_nums.extend(product(normal_nums, repeat = x))
        else:
            for x in range(length - 1, length + 2):
                possible_nums.extend(product(normal_nums, repeat = x))

        for y in possible_nums:
            num = int("".join(y))
            if abs(channel_num - num) + len(y) < answer:
                answer = abs(channel_num - num) + len(y)
        print(answer)

main()

 

 다른 사람 풀이 

1. Class를 사용한 풀이

class Remocon:
    def __init__(self):
        self.buttons = list(range(10))
    
    def distroy(self, b):
        self.buttons.remove(b)
    
    def __getitem__(self, n):
        l = len(self.buttons)
        result, digit = 0, 1
        while n >= l:
            result += self.buttons[n%l] * digit
            n //= l
            if self.buttons[0]:
                n -= 1
            digit *= 10
        result += self.buttons[n%l] * digit
        return result
    
    def least_button_push(self, target):
        if not self.buttons:
            result = float('inf')
        elif self.buttons == [0,]:
            result = target + 1
        elif self[0] > target:
            result = self[0] - target + 1
        else:
            lo, hi = 0, 10
            while self[hi] <= target:
                hi *= 10
            while hi - lo > 1:
                m = (lo + hi) // 2
                if self[m] < target:
                    lo = m
                else:
                    hi = m
            lower, higher = self[lo], self[hi]
            result = min(len(str(lower)) + abs(lower - target),
                        len(str(higher)) + abs(higher - target))
        return min(result, abs(target - 100))


remocon = Remocon()
target = int(input())
if int(input()):
    for button in map(int, input().split()):
        remocon.distroy(button)
print(remocon.least_button_push(target))

➡ 나는 고장난 버튼이 0이 아닌 경우에만 다음 input을 받도록 if-else문으로 나눴는데, 그냥 바로 if int(input()) 이라고 작성하면 되는 거였다! 그리고 least_button_push 메소드 구현을 정말.. 잘하신 것 같다. 뭔가 사람이 생각하는 알고리즘을 그대로 구현한 느낌.. 짱멋👍

 

2. 브루트 포스

import sys
input = sys.stdin.readline
MAX = 1000000

btn = [False] * 10
ch = int(input())
m = int(input())
a = list(map(int, input().split()))

for x in a:
    btn[x] = True

# 이동하려고 하는 채널까지 숫자를 눌러 이동 가능할 때, 
# 누르는 버튼의 개수를 반환
def possible(ch):
    if ch == 0:
        if btn[0]:
            return 0
        else:
            return 1
    len = 0
    while ch > 0:
        if btn[ch%10]:
            return 0
        len += 1
        ch //= 10
    return len

# 가장 처음에 보고 있는 채널은 100이기 때문에
# 초기값을 100에서 숫자 버튼을 누르지 않고 이동하는 횟수로 지정
answer = abs(ch - 50)

# 이동 가능한 모든 버튼을 검사
for i in range(100):
    len = possible(i)

    # 숫자를 눌러서 갈 수 있는 경우
    if len > 0:
        press = abs(i-ch) # +나 - 버튼을 몇 번 눌러야 하는지

        if answer > len + press:
            answer = len + press
print(answer)

➡ 음... 일단 최대한 가까운 숫자를 뽑아내는 건 같은데 그걸 while문으로 브루트 포스 방식으로 구현한 느낌이다.

 

출처 : https://enhjh.tistory.com/m/45