[백준 1107] 리모컨

1107번: 리모컨

알고리즘 : 브루트포스

난이도 : 골드Ⅴ

 

1. 문제요약

• 숫자 0~ 9번과 채널을 옮기는 +와 - 버튼이 있는 리모컨이 있는데, 리모컨의 숫자 버튼 일부가 고장난 상태이다.
• 입력으로 이동하려고 하는 채널번호 N(0이상 500,000이하의 정수)과 고장난 숫자의 개수 M(0이상 10이하의 정수), 그리고 고장난 숫자 번호 M개가 주어진다.
• 예를들어 5457번으로 이동하려고 하고, 숫자버튼 3개가 고장났는데 고장난 번호가 6,7,8이라면 입력은 다음과 같다.
  5457
  3
  6 7 8
• 현재 채널이 100번일때, 채널 N으로 이동하려면 버튼을 최소 몇번 눌러야 하는지 출력하는 프로그램을 작성한다.

2. 아이디어

• 예를들어, 위 예시에서는 5457과 가장 가까운 숫자 5455 또는 5459를 만들 수 있다. 5455에서 + 두번 누르면 5457이 되는데, 이 경우는 버튼을 총 6번 누른 것이다. (마찬가지로 5459에서 -버튼 두번 누르면 5457이 되고 이때도 버튼 누른 횟수는 6번이다) 현재 채널 100에서 +버튼을 5357번 눌러도 5457에 도달하지만, 6번이 최소 횟수이다.
• 결국 고장나지 않은 숫자 번호들을 활용해서 주어진 N과 가장 가까운 숫자를 만드는 것을 구현하는 것이 핵심이다. 따라서 사용가능한 번호를 조합하여 숫자 big, small을 구하는 것을 목표로 한다. 여기서 big은 N보다 큰 수중 가장 작은 것을 말하고, small은 그 반대의 경우이다.
• 사실 아이디어 자체는 별거 없고, 수많은 예외 케이스들을 빠짐없이 검토하는 것이 더 중요하다.

3. 구현과정

• 일단 N, M을 입력 받고, M개의 숫자를 리스트 cracked_num으로 입력받았으며, cracked_num으로부터 0부터 9까지 숫자중 고장나지 않은 숫자 리스트 possible_num을 만들었다고 가정하자. 그리고 possible_num의 원소중 최대값을 max_num, 최소값을 min_num에 저장했다고 하자.(물론 possible_num에 원소가 하나 이상 존재해야 한다)
• 우선 함수 bigger_num(x)를 정의한다. 이 함수는 possible_num의 원소에서 x보다 큰 것들 중 가장 작은 것을 리턴하는 함수인데, 만약 x보다 큰 것이 없다면 반환값이 없다. 구현은 매우 간단하므로 생략한다.
• 마찬가지로 possible_num의 원소에서 x보다 작은것들 중 가장 큰 것을 리턴하는 함수 smaller_num(x)를 정의한다.
• 다음으로 함수 find_big(xlist)를 정의한다. 여기서 xlist는 숫자 N을 리스트로 변환한 것이고(예를들어 5457이면 [5,4,5,7]을 말한다), 이 함수의 기능은 xlist가 나타내는 숫자보다 큰 것들 중 가장 작은 것을 리스트로 반환하는 것이다.
  • 일단 for문으로 range(len(xlist))를 i로 순회하면서, xlist[i]가 cracked_num에 속하는 최초의 i를 check에 저장하고 break한다.
  • 만약 끝까지 순회하였는데 cracked_num에 속하는 i가 없다면 xlist는 possible_num만으로 만들 수 있는 숫자라는 의미이다. 이 경우는 xlist 자체를 반환해주자.
  • 이제 check부터 0까지 i로 거꾸로 순회하면서 bigger_num(xlist[i])을 확인한다. 만약 xlist[i]의 bigger_num이 존재한다면, xlist보다 큰 숫자들중 가장 작은 숫자를 리스트로 표현하면 xlist[:i] + [bigger_num(xlist[i])] + [min_num] * (len(xlist)-i-1)이다. 이를 big에 저장하고 이를 return 해준다.
  • 만약 return으로 탈출하지 못하고 끝까지 순회하였다면 자릿수가 하나 올라가야 한다. 일단 possible_num의 원소가 0밖에 없다면 xlist보다 더 큰 수를 만들 수 없으므로 빈 리스트 []를 반환하고, 이외의 경우를 살핀다.
  • 자릿수가 올라갔을때, 맨 앞자리수 first에는 최소값을 넣어주어야 큰 수들 중 가장 작은수가 된다. 다만 min_num이 0일 수 도 있으므로, min_num이 0이 아닌 경우에만 first = min_num이다. 만약 min_num이 0이라면 first = min(possible_num[1:])이다. 
  • first가 정해졌다면, big = [first] + [min_num] * len(xlist)가 되고, 이를 return해준다.
• 유사하게 xlist가 나타내는 숫자보다 작은 것들 중 가장 큰 것을 리스트로 반환하는 find_small(xlist)를 정의한다.
• 마지막으로 리스트를 숫자로 변환하는 함수 list_to_num(xlist) 함수까지 정의하면 필요한 모든 함수를 정의하였다.
• 이제 정답 answer를 구할 차례이다. 우선 answer = abs(100 - n)이라 하자. 이는 채널 100에서 +- 버튼만으로 이동한 경우를 의미한다.
• possible_num이 비어있지 않은 경우에만 big과 small을 구할 수 있으므로 이를 if문으로 체크한다.
  • 우선 n을 리스트화 한 것을 nlist라 하고, n보다 큰 것들중 가장 작은 수를 리스트화한 biglist, 반대경우인 smalllist를 각각 find_big(nlist), find_small(nlist)로 구한다.
  • biglist가 비어있지 않은 경우여야 숫자 big이 존재하므로, if문으로 체크하고 list_to_num(biglist)로 big을 구한다. 이 big숫자의 길이와 abs(big - n)을 더하면 총 누른 버튼의 수가 된다. 이를 기존 answer와 비교하여 더 작은 것을 answer에 저장한다.
  • small의 경우도 마찬가지의 프로세스를 거쳐 answer를 업데이트 한다.
• answer를 출력하면 구하는 답이 된다.

4. 파이썬 코드

def bigger_num(x):
    for i in possible_num:
        if i > x:
            return i
    else:
        return

def smaller_num(x):
    for i in reversed(possible_num):
        if i < x:
            return i
    else:
        return

def find_big(xlist):
    for i in range(len(xlist)):
        if xlist[i] in cracked_num:
            check = i
            break
    else:
        return xlist
    for i in reversed(range(check + 1)):
        if bigger_num(xlist[i]):
            big = xlist[:i] + [bigger_num(xlist[i])] + [min_num] * (len(xlist) - i - 1)
            return big
    else:
        if possible_num[-1] == 0:
            return []
        else:
            first = min_num if min_num else min(possible_num[1:])
            big = [first] + [min_num] * len(xlist)
            return big

def find_small(xlist):
    for i in range(len(xlist)):
        if xlist[i] in cracked_num:
            check = i
            break
    else:
        return xlist
    for i in reversed(range(check + 1)):
        if smaller_num(xlist[i]) != None:
            small = xlist[:i] + [smaller_num(xlist[i])] + [max_num] * (len(xlist) - i - 1)
            return small
    else:
        if max_num and len(xlist) > 1:
            small = [max_num] * (len(xlist) - 1)
            return small
        else:
            return []

def list_to_num(xlist):
    tmp = ""
    for i in xlist:
        tmp += str(i)
    return int(tmp)

n = int(input())
m = int(input())
cracked_num = []
if m:
    cracked_num = list(map(int, input().split()))
possible_num = []
for i in range(10):
    if i not in cracked_num:
        possible_num.append(i)

answer = abs(100 - n)
if possible_num:
    max_num, min_num = max(possible_num), min(possible_num)
    nlist = list(map(int, str(n)))
    biglist, smalllist = find_big(nlist), find_small(nlist)
    if biglist:
        big = list_to_num(biglist)
        answer = min(answer, abs(big - n) + len(str(big)))
    if smalllist:
        small = list_to_num(smalllist)
        answer = min(answer, abs(small - n) + len(str(small)))
print(answer)