📌 문제
문제도 이해하기 쉽고 재밌는 문제였다.
이 정도 문제가 아니라 정말 정말 길고 꼬아낸 문제들은 읽기가 너무 힘들담..
👉 문제 요약
버튼 0 ~ 9
+ 누르면 +1, - 누르면 -1, 0에서는 변하지 않음
수빈이가 지금 보고 있는 채널 100, 이동하려고 하는 채넗 N (채널은 무한대)
어떤 버튼이 고장났는지 주어졌을 때, 채널 N으로 이동하기 위해서 버튼을 최소 몇 번 눌러야하는지 구해라!
입력
수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)
고장난 버튼의 개수 M (0 ≤ M ≤ 10)
출력
채널 N으로 이동하기 위해 버튼을 최소 몇 번 눌러야 하는지를 출력✏️ 풀이 - 1
import sys
input = sys.stdin.readline
current_channel = 100
# 수빈이가 이동하려고 하는 채널
N = int(input())
# 이동할 필요가 없다면
if (N == current_channel):
print(0)
sys.exit()
# 고장난 버튼의 개수 0 ~ 9 사이
M = int(input())
# 고장난 버튼 리스트
if M > 0:
broken_btn_list = list(map(int, input().split()))
else:
broken_btn_list = []
# 사용할 수 있는 버튼 리스트
btn_list = [str(i) for i in range(10) if i not in broken_btn_list]
# 숫자 버튼으로 이동 가능한지 체크
def can_move(channel):
for ch in str(channel):
if ch not in btn_list:
return False
return True
# 현재에서 목표 채널까지 +/- 버튼만을 눌러서 이동하는 최대 횟수
min_press = abs(N - current_channel)
for i in range(1000000):
if can_move(i):
min_press = min(min_press, len(str(i)) + abs(i - N))
# len(str(i)) = 채널 i로 이동하기 위해 숫자 버튼을 누르는 횟수
# abs(i - N) = +/-를 눌러서 이동하는 횟수
# 숫자 버튼을 눌러서 i채널로 이동한 뒤 +/- 버튼으로 N까지 이동
print(min_press)⏰ 시간복잡도 O(n)
0부터 999,999까지의 채널을 반복하여 가능한 채널을 생성하므로 O(N)
✏️ 풀이 - 2
# 현재 채널
current_channel = 100
# 수빈이가 이동하려는 채널
N = int(input())
# 고장난 버튼의 개수
M = int(input())
# 고장난 버튼 리스트
if M > 0:
broken_buttons = set(map(int, input().split()))
else:
broken_buttons = set()
# 가능한 채널을 생성하는 함수
def possible_channels():
for channel in range(1000001): # 0부터 1,000,000까지의 채널 생성
for digit in str(channel):
if int(digit) in broken_buttons:
break
else:
yield channel # 값 반환
# 가능한 채널 중 목표 채널에 가장 가까운 채널을 찾는 함수
def find_nearest_channel():
min_press = abs(N - current_channel) # 현재 채널에서 목표 채널까지 +/- 버튼을 누르는 횟수
for channel in possible_channels():
min_press = min(min_press, len(str(channel)) + abs(channel - N))
return min_press
# 목표 채널까지 최소 버튼 누름 횟수 출력
print(find_nearest_channel())⏰ 시간복잡도 O(n)
0부터 999,999까지의 채널을 반복하여 가능한 채널을 생성하므로 O(N)
풀이 1은 0부터 999,999까지의 모든 채널을 생성하고, 고장난 버튼을 포함하지 않는 채널만을 선택하는 방식
풀이 2는 고장난 버튼을 포함하지 않는 필요한 채널만을 생성하는 방식으로 채널 생성이 풀이1 보다 더 효율적이다.
대표적인 브루트푸스 유형의 문제로 이동하려는 최대 채널은 500,000이므로 고장난 버튼이 없는 경우에도 최대 6자리(999,999)까지의 채널 번호를 가질 수 있으므로, 모든 경우의 채널을 탐색할때 0 ~ 1,000,000까지 고려해준다.
🌟 yield 문법
iterator를 반환
-> iterator란 반복 가능한 객체(iterable)에서 값을 하나씩 가져오는 객체
ex_ list, string, tupleyield 문법은 함수가 iterator를 반환하는 것을 가능하게 한다. 함수가 이터레이터를 반환하면, 함수의 실행 상태를 기억하고 다음 값을 생성할 수 있다.
이터레이터를 반환하는 함수를 호출하여 값을 가져올 때마다 함수는 일시 중지되고 값을 생성하여 반환한 뒤, 다시 시작하여 다음 값을 생성할 준비를 한다.
-> possible_channels() 함수는 실제로 호출될 때까지 채널을 생성하지 않고 필요한 채널을 요청할 때마다 생성한다.정리
return 문은 함수를 호출한 곳으로 값을 반환하고 함수의 실행을 종료한다.
yield 문은 함수가 이터레이터(iterator)를 반환하게 한다. 함수가 yield를 만나면 현재 상태를 유지하고 값을 생성하여 반환한다. 그리고 다음 호출 때는 yield 문 이후의 코드부터 실행하여 다음 값을 생성한다. 이것이 🌟 제너레이터(generator)라 불리는 개념! 따라서 yield를 사용하면 함수는 여러 번 값을 생성할 수 있고, 함수의 실행 상태가 유지된다.
=> 함수가 값을 한 번만 반환하면서 종료되어도 되는 경우에는 return을 사용, 함수가 여러 번 값을 생성하고 상태를 유지해야 하는 경우에는 yield를 사용!
