문제 원본 링크 : 백준 1107번 문제

원래 계획은 다양한 알고리즘 분류 문제를 풀어보며 알고리즘의 유형들을 탐색해볼 생각이었지만, 브루트포스 알고리즘 문제를 푸는 것에 연달아 실패한 이후 먼저 브루트포스 알고리즘부터 정복해야겠다는 오기(?)가 생겼다.

그래서 이번에도 알고리즘 분류의 브루트포스 알고리즘 탭으로 들어가 문제를 하나 골랐다.

첫 시도, 잘못된 코드

#백준 1107번 문제

# 1. 사용 가능한 숫자로 주어진 채널과 가장 가까운 숫자를 만든다.
# 2. 그렇게 만든 숫자에서 + 또는 -를 눌러 주어진 채널로 이동한다.
# 3. 이 방식에서 버튼을 누른 횟수와, 채널 100에서 오로지 + 또는 -를 눌러 주어진 채널로 이동할 때 버튼을 누르는 횟수를 비교하여 횟수가 더 적은 방법을 찾는다.
# 4. 만약 주어진 채널이 100일 경우 횟수 0을 출력한다.
# 5. 만약 0에서 9까지의 모든 버튼이 다 고장났을 경우 주어진 채널과 100의 차를 출력한다.
# 6. 만약 아무 버튼도 고장나지 않았을 경우 주어진 채널의 자릿수를 출력한다.

goal = int(input())
err_count = int(input())
if err_count == 0:
  pass
else:
  err_buttons = list(map(int, input().split()))

#사용 가능한 숫자로 주어진 채널과 가장 가까운 숫자 만들기
def closest_ch(target_ch, err_buttons):
  closest = []
  if target_ch < 10:
    upside_range = list(range(target_ch, 10))
  else:
    upside_range = list(range(target_ch, target_ch*2+1))
  downside_range = list(reversed(range(0, target_ch)))
  for n in upside_range:
    check = True
    for i in err_buttons:
      if str(i) in str(n):
        check = False
        break
    if check == False:
      continue
    closest.append(n)
    break
  for n in downside_range:
    check = True
    for i in err_buttons:
      if str(i) in str(n):
        check = False
        break
    if check == False:
      continue
    closest.append(n)
    break
  if len(closest) == 1:
    return closest[0]
  else:
    if abs(closest[0]-target_ch) < abs(closest[1]-target_ch):
      return closest[0]
    else:
      return closest[1]

def solve():
  if goal == 100:
    print('0')
  elif err_count == 10:
    print(abs(goal - 100))
  elif err_count == 0:
    print(len(str(goal)))
  else:
    closest_num = closest_ch(goal, err_buttons)
    route_1 = abs(closest_num - goal) + len(str(closest_num))
    route_2 = abs(goal - 100)
    if route_1 < route_2:
      print(route_1)
    else:
      print(route_2)

solve()

문제 해결 접근 방식은 다음과 같다.

• 1. 사용 가능한 숫자로 주어진 채널과 가장 가까운 숫자를 만든다.
• 2. 그렇게 만든 숫자에서 + 또는 -를 눌러 주어진 채널로 이동한다.
• 3. 이 방식에서 버튼을 누른 횟수와, 채널 100에서 오로지 + 또는 -를 눌러 주어진 채널로 이동할 때 버튼을 누르는 횟수를 비교하여 횟수가 더 적은 방법을 찾는다.
• 4. 만약 주어진 채널이 100일 경우 횟수 0을 출력한다.
• 5. 만약 0에서 9까지의 모든 버튼이 다 고장났을 경우 주어진 채널과 100의 차를 출력한다.
• 6. 만약 아무 버튼도 고장나지 않았을 경우 주어진 채널의 자릿수를 출력한다.

여느 때와 같이 코드를 전부 작성한 후에는 '이번에는 진짜 틀릴 리가 없어!' 하는 근거없는 자신감과 함께 채점을 시작했으나...

도저히 혼자만의 힘으로는 역부족이라 생각해 숨고에서 코딩 과외 선생님을 구해 피드백을 받았다.

수정한 코드

#백준 1107번

#문제 해결 논리
#목표채널 : 100 -> 이동할 필요 없음. 버튼 누르는 횟수 0
#목표채널 : 100 이외의 숫자 -> 루트1과 루트2 비교 후 적은 횟수 채택
    #루트1 : 현재채널 100에서 목표채널로 +/-로만 이동하는 경우
    #루트2 : 사용가능한 숫자버튼을 활용해 목표채널과 가장 가까운 채널로 이동 후 목표채널까지 +/-를 활용해 이동하는 경우
        #고장난 버튼 0개 : 숫자버튼만 눌러 목표채널로 바로 이동
        #고장난 버튼 10개 : +/- 버튼만 눌러 목표채널로 이동
        #고장난 버튼 9개(숫자 0 버튼만 사용 가능) : 숫자 0으로 이동, 목표채널까지 +/-

def route_1(target_ch:int) -> int:
    return abs(target_ch - 100)

def closest_num(target_ch:int, err_buttons:list) -> int:
    closest_number = 1000000
    err_buttons_set = set(map(str, err_buttons))

    for num in range(1000001):
        num_set = set(str(num))
        if err_buttons_set.isdisjoint(num_set):
            if abs(closest_number - target_ch) > abs(num - target_ch):
                closest_number = num
    return closest_number

def route_2(target_ch:int, err_buttons_num:int, err_buttons:list) -> int:
    ans = 0
    if err_buttons_num == 0:
        ans = len(str(target_ch))
    elif err_buttons_num == 10:
        ans = abs(target_ch - 100)
    elif err_buttons_num == 9 and 0 not in err_buttons:
        ans = target_ch + 1
    else:
        closest_ch = closest_num(target_ch, err_buttons)
        ans = len(str(closest_ch)) + abs(closest_ch - target_ch)
    return ans

def solve(target_ch:int, err_buttons_num:int, err_buttons:list) -> None:
    if target_ch == 100:
        print(0)
        return
    else:
        print(min(route_1(target_ch), route_2(target_ch, err_buttons_num, err_buttons)))
        return

target_ch = int(input())
err_buttons_num = int(input())
if err_buttons_num:
    err_buttons = list(map(int, input().split()))
else:
    err_buttons = []

solve(target_ch, err_buttons_num, err_buttons)

피드백을 통해 배운 것 3가지

• 임의의 채널로 이동할 때 고장난 숫자버튼을 사용하지 않고 이동할 수 있는 지 여부

  set( ) 자료형 및 메소드 활용

  • 이동하려는 채널에 활용된 숫자들의 집합과 고장난 버튼의 숫자 집합에 교집합이 없으면 됨
  • err_buttons_set.isdisjoint(num_set)
  • 교집합이 없으면 True, 있으면 False

• 함수를 정의할 때 매개변수의 자료형과 출력값의 자료형 표시 방법

  • def route_1(target_ch:int) -> int:
  • def solve(target_ch:int, err_buttons_num:int, err_buttons:list) -> None:

• map( )은 입력 받을 때만 활용하는 것이 아니다. 배열의 각 요소들의 자료형을 한 번에 바꾸고 싶을 때 활용

  배열의 각 요소 자료형을 한 번에 바꿀 때 활용

  • 리스트에 있는 고장난 버튼의 숫자들의 자료형을 문자열로 바꾸어야 할 필요가 있는 상황
  • err_buttons_set = set(map(str, err_buttons))