-
[연습 문제] 숫자 타자 대회 ( 파이썬 )코딩 테스트/프로그래머스 2023. 6. 6. 16:56
문제 설명
https://school.programmers.co.kr/learn/courses/30/lessons/136797
문제 풀이
- 번호에서 다른 번호로 이동할 때 드는 가중치들 미리 계산 (dist_num 함수)
- 각 단계별(numbers 각 자리수) 탐색 시 생성 될 수 있는 가중치들을 계산
- 왼손을 움직일 경우 가중치는 d[left][num] , 큐에 담을 수는 num,right
- 오른손을 움직일 경우 가중치는 d[right][num] , 큐에 담을 수는 left,num
- 따로 조건을 달지 않을 경우 생성되는 경우의 수는 2^n 이고 최대 100,000의 길이이므로 예외를 둬야함
- 최단거리 알고리즘을 활용해봄
- 각 자릿수를 행으로 두는 거리 기록을 사용
- dist => [n자릿수][ left가 움직일 수 있는 10가지 ] [ right가 움직일 수 있는 10가지 ]
- 탐방할 가중치가 기록 값보다 클 경우 패스하는 것으로 예외 처리함
소스 코드
from collections import deque import heapq def dist_num(): #각 번호들의 이동 가중치 계산 함수 dx = [0,0,-1,1,1,1,-1,-1] dy = [-1,1,0,0,1,-1,1,-1] cell = [[0]*3 for i in range(4)] for i in range(3): for j in range(3): cell[i][j] = i*3+j+1 cell[-1][0],cell[-1][2] = 11,11 dist = [[100]*10 for i in range(10)] for i in range(4): for j in range(3): if cell[i][j]>10: continue t = cell[i][j] q = deque() q.append((0,i,j)) dist[t][t]=1 while(q): cnt,x,y = q.popleft() cur = cell[x][y] for k in range(8): nx = x + dx[k] ny = y + dy[k] if nx<0 or ny<0 or nx>=4 or ny>=3: continue next = cell[nx][ny] move = 2 if k<4 else 3 if next==11: continue if dist[t][next]<cnt+move: continue dist[t][next]= cnt+move q.append((cnt+move,nx,ny)) return dist def solution(numbers): INF = int(1e9) answer = INF numbers = list(map(int,numbers)) n=len(numbers) d=dist_num() distant = [[[INF]*10 for i in range(10)] for j in range(n+1)] distant[0][4][6] = 0 q = [] heapq.heappush(q,(0,0,4,6)) while(q): w, next, left, right = heapq.heappop(q) if next == n: return w num = numbers[next] if num in [left,right]: if distant[next+1][left][right]>w+1: distant[next+1][left][right]=w+1 heapq.heappush(q,(w+1,next+1,left,right)) else: if distant[next+1][num][right]>w+d[left][num]: distant[next+1][num][right]=w+d[left][num] heapq.heappush(q,(w+d[left][num],next+1,num,right)) if distant[next+1][left][num]>w+d[right][num]: distant[next+1][left][num]=w+d[right][num] heapq.heappush(q,(w+d[right][num],next+1,left,num)) return answer print(solution("1756"))
오답노트
- 현재 자리에서 다음 자리로의 거리는 미리 구하기 가능(탐색이든 수학적 접근이든)
- 시간 초과의 관건이 되는 것은 탐색 가지 수
- 각 자리 수마다 왼손으로 누를 지 오른손으로 누를 지 선택 해야 하므로 총 탐색을 한다면 2^100,000이 나옴
- 이것을 줄이기 위해 처음 생각한 것은 힙큐
- 최단 거리 알고리즘 접목 시켜서 다음으로 탐색할 숫자까지의 가중치가 현재 탐색+dist보다 크다면 값을 업데이트, 그렇지 않다면 continue
- 이렇게 했더니 일단 테케에서 시간 초과는 안뜸. 틀린 이유 찾아보기 ing
왼손 오른손으로 탐색한다는 것을 왼손은 0 오른손은 1로만 지정해서 틀림
'코딩 테스트 > 프로그래머스' 카테고리의 다른 글
[DFS/BFS] 아이템 줍기 (파이썬) - 진행 중 (1) 2023.06.13 [카카오] 블록 이동하기 ( 파이썬 ) (0) 2023.06.10 [탐색] 퍼즐 조각 채우기 (파이썬) (0) 2023.06.02 [탐색] 미로 탈출 명령어 ( 파이썬 ) (0) 2023.05.14 [이분 검색] 외벽 점검 (파이썬, 카카오) (1) 2023.05.12