[백준] 1107 리모컨 - Python

 

1107번: 리모컨

 

- 문제 설명

• TV를 보다 채널을 돌리려고하는데 고장난 버튼이 있다.
• 고장나지 않은 버튼과 +, - 버튼을 눌러 보고싶은 채널로 이동한다.
• 초기에 채널은 100번채널이다. 100번에서 +, - 버튼으로 이동한 횟수와
  숫자 버튼으로 이동한 후 +, - 로 다시 이동한 경우 중 최솟값을 찾는다.

 

- 입출력 예시

 

- 처음 접근방법

• 최초에 누르려는 버튼의 길이만큼 버튼을 눌러 목표 채널과 가장 가까운채널을 찾는다.
• 그래서 고장나지 않은 버튼만 들어있는 리스트에서 중복순열(product)를 사용해 채널을 탐색하였다.
• 테스트케이스는 전부 맞았지만 틀렸다.

 

- 실패 코드

from itertools import product

chanal = int(input())       # 목표채널
n = int(input())            # 고장난 버튼 개수
broken = list(map(int, input().split()))    # 고장난 버튼들

# 고장난 버튼 체크
butten = []
for i in range(10):
    if i not in broken:
        butten.append(i)

# 채널의 길이를 요소의 개수로한 중복순열
a = product(butten, repeat=len(str(chanal)))
mini = (chanal, 0)

# 중복순열의 요소마다 10의 n제곱하여 더한 수와 목표채널과의 차이를 계산
for i in a:
    l = len(i)-1
    rlt = 0
    for j in i:
        rlt += j * (10 ** l)
        l -= 1
    if mini[0] > abs(rlt-chanal):
        mini = (abs(rlt-chanal), rlt)

# cnt는 채널의 길이만큼 눌렀음
cnt = len(str(chanal))
# 현재 채널과 목표채널의 차이를 cnt에 더해줌
cnt += abs(mini[1]-chanal)

# 만약 초기채널값 100에서 출발했을때 버튼을 덜눌러도 된다면
# 100과 목표채널의 차이 출력
if abs(chanal - 100) < cnt:
    print(abs(chanal-100))
else:
    print(cnt)

 

- 새로운 접근

• 어렵게 생각하지말고 브루투포스 방식으로 탐색해보기로했다.
• 처음에 답을 100번 채널에서 목표채널로 이동한 값으로 저장한다.
• 1000000까지 순회하면서 최소값을 갱신한다.
• 1000000까지 순회하는 이유는 목표채널은 최대 500000이지만 채널은 무한대이고
  그 이상 순회하는건 100번에서 이동하는 값이 더 가까울 것이다.

 

- 풀이 코드

chanal = int(input())       # 목표채널
n = int(input())            # 고장난 버튼 개수
broken = []
if n:
    broken = list(map(int, input().split()))    # 고장난 버튼들
# 초기 채널 100에서 목표채널까지의 차를 ans에 저장
ans = abs(chanal-100)
# 1000000까지 순회
for num in range(1000001):
    for i in str(num):  # 순회하는 숫자에 고장난 버튼의 숫자가 있다면 break
        if int(i) in broken:
            break
    # 고장난 버튼이 없었다면 현재 num의 길이와 num과 목표채널의 차이를 더한값과
    # 기존 답을 비교하여 최솟값 갱신
    else:
        ans = min(ans, len(str(num)) + abs(num-chanal))
        
print(ans)

 

 

최근에 정보처리기사 필기준비와 이번주 주말 SQLD 시험준비로 알고리즘 공부를 거의 못했다ㅠㅠ

주말에 SQLD까지 끝내면 다시 열심히 알고리즘에 집중해야겠다.