[백준][python] 1107번: 리모컨

2022-05-01 4 분 소요

1107번: 리모컨

백준(boj) 1107번

문제

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

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

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

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

입력 조건

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

출력 조건

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

첫 번째 시도 .(2022년 2월)

channel = int(input())
m = int(input())

uf_buttons = set(map(int,input().split()))
buttons = set([i for i in range(10)])

buttons= list(buttons - uf_buttons)
buttons=sorted(buttons)

if len(buttons) != 0:
    #case1
    channel_1=0
    for num in str(channel):
        channel_1 *=10
        gap=11
        best_button=11
    
        for button in buttons:
            if gap > abs(int(num)-button):
                gap = abs(int(num)-button)
                best_button = button
        channel_1 += best_button

    if int(str(channel_1)[0]) > int(str(channel)[0]):
        channel_1 = str(channel_1)[0]
        for i in range(len(str(channel))-1):
            channel_1 += str(buttons[0])
        channel_1 = int(channel_1)

    if int(str(channel_1)[0]) < int(str(channel)[0]):
        channel_1 = str(channel_1)[0]
        for i in range(len(str(channel))-1):
            channel_1 += str(buttons[-1])
        channel_1 = int(channel_1)
    
    #case2    
    channel_2=0
    if len(buttons) >= 2:
        if buttons[0]==0:
            channel_2 += buttons[1]
        else:
            channel_2 += buttons[0]
    else:
        channel_2 += buttons[0]
    for i in range(len(str(channel))):
        channel_2 *=10
        channel_2 += buttons[0]

    #case3
    channel_3 = 10000001
    if channel >= 10:
        channel_3=0
        for i in range(len(str(channel))-1):
            channel_3 *=10
            channel_3 += buttons[-1]
    
    #case4
    channel_4=0
    temp = round(channel,-1)
    for num in str(temp):
        channel_4 *=10
        gap=11
        best_button=11
    
        for button in buttons:
            if gap > abs(int(num)-button):
                gap = abs(int(num)-button)
                best_button = button
        channel_4 += best_button

    if int(str(channel_4)[0]) > int(str(temp)[0]):
        channel_4 = str(channel_4)[0]
        for i in range(len(str(temp))-1):
            channel_4 += str(buttons[0])
        channel_4 = int(channel_4)

    if int(str(channel_4)[0]) < int(str(temp)[0]):
        channel_4 = str(channel_4)[0]
        for i in range(len(str(temp))-1):
            channel_4 += str(buttons[-1])
        channel_4 = int(channel_4)

    least_move=[]
    for make_channel in [channel_1,channel_2,channel_3,channel_4]:
        least_move.append(abs(make_channel-channel)+len(str(make_channel)))
    least_move.append(abs(100-channel))
    result = min(least_move)
else:
    result = abs(channel-100)
    
print(result)

»intput

5457
3
6 7 8

»output

fail

🌝 Thinking

[아이디어]

고장 나지 않은 버튼들을 이용하여 가고 싶은 채널에 가장 근사한 숫자를 만든다.

(가고 싶은 채널의 각자리의 숫자를 가용 버튼과 비교하여 가장 오차가 적은 숫자를 채택하여 채널을 만듬.)
1에서 생성된 번호와 가고 싶은 채널의 오차는 채널 위/아래 버튼으로 도달 시킴.
위의 케이스와 100번 채널에서 가고 싶은 채널의 차이 중 최소 횟수를 채택함.

[틀린이유]

1~2에서 생성된 채널은 자릿수에서 자유롭지 못한다.

(예를들면, 1001번을 틀고 싶을 때 999번에서의 접근이 1111에서의 접근보다 좋다. 사용 가능 버튼이 1,9일 때 )

이를 처리해주기 위해서는 효율적이지 못한 코드가 늘어난다.

그 다음 각 자리에서의 오차만 줄이는 접근은 그 숫자로부터 큰 수로부터 접근하는지 작은 수로 접근할지,

예측하기 어렵다.(가능하더라도 효율적이지 못함.)

따라서 반례가 존재했다…

이 풀이방법에 얽매이어 있어서 유사한 풀이코드로는 풀수 없었다……..

두 번째 시도 .(2022년 4월 28일)

#채널/ 고장난 버튼 수/ 고장난 버튼/ 정상 버튼
channel = int(input())
broken_num = int(input())

if broken_num != 0:
    broken = set(map(int,input().split()))
    button = list(set(range(10)) - broken)
else:
    button = list(range(10))
    
click = []
#버튼이 전부다 고장이 났다면? 직접이동
if broken_num == 10:
    print(abs(channel - 100))
#버튼이 전부 멀쩡하다면? 버튼이동 vs 직접이동
elif broken_num == 0:
    if len(str(channel)) < abs(channel - 100):
        print(len(str(channel)))
    else:
        print(abs(channel - 100))
#남은 버튼 vs 직접이동
else:
    #작은 채널
    for make in range(channel,-1,-1):
        channel_len = len(str(make))
        count = 0
        test = make
        if make == 0 and 0 in button:
            click.append(channel + 1)
        while test!=0:
            if test % 10 in button:
                count += 1
                test //= 10
            else:
                break
        if channel_len == count:
            click.append(channel - make + channel_len)
            break
    #큰채널
    for make in range(channel+1,1000001):
        channel_len = len(str(make))
        count = 0
        test = make
        while test!=0:
            if test % 10 in button:
                count += 1
                test //= 10
            else:
                break
        if channel_len == count:
            click.append(make - channel + channel_len)
            break

    #100에서 직접이동
    channel_direct = abs(channel - 100)
    click.append(channel_direct)
    print(min(click))

»intput

5457
3
6 7 8

»output

success

🌝 Thinking

[아이디어]

반례를 피하기 위해서

모든 버튼이 멀쩡할 때 (버튼 입력(클릭 횟수) vs 100에서 직접 접근)

모든 버튼이 망가졌을 때 (100에서 직접 접근)

버튼이 1개 ~ 9개 망가졌을 때 (직접 접근 vs 만들 수 있는 큰 채널 vs 만들 수 있는 작은 채널)

와 같이 3가지의 큰 분기로 나누어 생각을 하였다. (이게 정말 중요했다..!)
가고싶은 채널에서 1씩 증가시켜 버튼으로 만들 수 있는 가장 최소값을 찾음(큰 채널)
0에서 부터 가고 싶은 채널까지 1씩 증가를 시켜 버튼으로 만들 수 있는 가장 큰 값을 찾음 (작은 채널)

upper bound와 lower bound 찾는 느낌 ?! 이 엄청난 시간 초과를 만들어 낼 줄 알았는데 그렇지 않았음.

💡 깨달은 점.

브루트포스 알고리즘 문제였는데 첫 번째 시도방식은 해당 알고리즘의 이름에 걸맞지 않았다.

정말 직접 다 찾아서, 확인을 하면 되었다.
내가 만든 코드가 반례가 많다면, 전체 코드의 큰 분기문을 손보면 방법이 있다는 사실을 알게 되었다.

Twitter Facebook LinkedIn

[백준][python] 1107번: 리모컨

1107번: 리모컨

문제

입력 조건

출력 조건

🌝 Thinking

🌝 Thinking

💡 깨달은 점.

공유하기

댓글남기기

참고

[Operating System] 단기 스케줄러 CPU 스케줄링!

[Operating System] 프로세스는 어떻게 다루어지는가?

[Network] 네트워크

알고리즘 테스트 준비를 위한 C++ 시스템 입력 방법 모음