2021. 2. 23. 11:52ㆍ코딩테스트
programmers.co.kr/learn/courses/30/lessons/72415
코딩테스트 연습 - 카드 짝 맞추기
[[1,0,0,3],[2,0,0,0],[0,0,0,2],[3,0,1,0]] 1 0 14 [[3,0,0,2],[0,0,1,0],[0,1,0,0],[2,0,0,3]] 0 1 16
programmers.co.kr
굉장히 삽질을 많이하고 문제가 더럽고 시간초과가 계속나서 PS 갤러리에가서 질문까지해서 해결했습니다.
gall.dcinside.com/mgallery/board/view/?id=ps&no=12360&page=1
2021 카카오 코테 카드 짝 맞추기 풀다가 막혔는데 질문좀 - PS 갤러리
https://programmers.co.kr/learn/courses/30/lessons/72415일단 이거구요from queue import PriorityQueue as pqfrom copy import deep
gall.dcinside.com
댓글 달아주신 두분께 감사의 인사 드립니다.
정답 코드는 글 제일 아래쪽에 있습니다.
0. 정답이 나온 코드를 제외하면 모두 13, 14, 15, 16, 22, 23, 25번에서 시간초과가 났습니다.
1. 디테일한 문제 설명은 패스
첫번째 빡치는 부분, 처음에는 8가지 캐릭터라면서 조건이랑 풀이는 6개임
2. 문제 해결 방향 설정
- (x, y)에서 (nx, ny)에 있는 카드를 찾으러 가는 최소 횟수를 구함 (코드에서 함수 go)
- 문제풀이처럼 카드 개수가 N개 일 때, N개 순열을 만듦 (함수 back)
- N개 순열에서 최소 경로를 계속 구함 (함수 back에서 if문 안에 내용)
3. 실패코드
from queue import PriorityQueue as pq
from copy import deepcopy
def solution(board, r, c):
answer = 10**6
SIZE = 4
DELTAS = ((1, 0), (0, 1), (-1, 0), (0, -1))
def _is_in_range(r, c):
return 0 <= r < SIZE and 0 <= c < SIZE
def _is_empty(r, c, bd):
return bd[r][c] == 0
def _yield_moves(d, r, c, bd):
for dr, dc in DELTAS:
nr = r + dr
nc = c + dc
if not _is_in_range(nr, nc):
continue
yield(d+1, nr, nc)
while _is_empty(nr, nc, bd) and _is_in_range(nr+dr, nc+dc):
nr = nr + dr
nc = nc + dc
yield(d+1, nr, nc)
def go(r, c, nr, nc, bd):
q = pq()
q.put((0, r, c))
visited = set()
visited.add((0, r, c))
while q:
d, r, c = q.get()
if (r, c) == (nr, nc):
return d
for next_cursor in _yield_moves(d, r, c, bd):
if next_cursor not in visited:
q.put(next_cursor)
visited.add(next_cursor)
return 0
cand = []
for i, arr in enumerate(board):
for j, val in enumerate(arr):
if val != 0:
cand.append((val, i, j))
l = len(cand)
used = [0] * l
def back(chosen, board, moves):
nonlocal answer
if len(chosen) == l:
x, y = r, c
moves = 0
m = []
bd = deepcopy(board)
for card, j, k in chosen:
moves += go(x, y, j, k, bd)
bd[x][y] = 0
x, y = j, k
answer = min(answer, moves+l)
return
for i in range(l):
if not used[i]:
if len(chosen)%2 ==0 or (chosen and chosen[-1][0] == cand[i][0]):
chosen.append(cand[i])
used[i] = 1
back(chosen, board, moves)
used[i] = 0
chosen.pop()
return
back([], board, 0)
return answer
최소 횟수 구하는 부분을 priority Queue로 구현
back함수부분에 첫번째 if문은 종료조건
아래 for문은 chosen 고르는 부분
가장 안쪽 if문은 고르는 과정에서 시간이 많이 생기나해서 조건을 추가했는데 결과에 차이는 없었음
4. 두번째 실패코드
cand = []
for i, arr in enumerate(board):
for j, val in enumerate(arr):
if val != 0:
cand.append((val, i, j))
cand = sorted(cand)
l = len(cand)//2
used = [0] * l
def back(chosen, x, y, board, moves):
nonlocal answer, used, l
if len(chosen) == l:
answer = min(answer, moves+2*l)
return
for i in range(l):
if not used[i]:
chosen.append(cand[i])
used[i] = 1
nx, ny = cand[2*i][1], cand[2*i][2]
mx, my = cand[2*i+1][1], cand[2*i+1][2]
tmp = deepcopy(board)
n = go(x, y, nx, ny, tmp)
board[nx][ny] = 0
n += go(nx, ny, mx, my, board)
board = deepcopy(tmp)
m = go(x, y, mx, my, board)
board[mx][my] = 0
m += go(mx, my, nx, ny, board)
board[nx][ny] = 0
back(chosen, nx, ny, board, moves+m)
back(chosen, mx, my, board, moves+n)
board = deepcopy(tmp)
used[i] = 0
chosen.pop()
return위에는 생략, 후보카드의 좌표인 cand 리스트를 정렬해서 AABBCC가 되도록 만듦
종료조건때마다 계산하는게 오래걸리나 싶어서 파라미터로 moves를 넘겨가면서 구현
이것도 시간초과
5. 조언
ps갤러리에 질문을하고 3가지 가능성에 조언을 들음
하나. queue에 있는 priorityQueue 대신에 heapq를 써볼것
둘. deepcopy()가 오래 걸릴 것
셋. 우선순위큐 대신 deque를 써볼것
결과적으로 첫째, 둘째 조언은 맞는애들 시간은 줄어들었으나 시간초과나는애들은 그대로
우선순위큐 대신 deque를 쓴 부분에서 정답이 나옴
그런데 첫번째 실패코드는 우선순위큐를 deque로 바꿔도 시간초과가 나왔는데
두번째 실패코드에서는 정답이 나옴
6. 정답코드
from collections import deque as dq
from copy import deepcopy
def solution(board, r, c):
answer = 10**6
SIZE = 4
DELTAS = ((1, 0), (0, 1), (-1, 0), (0, -1))
def _is_in_range(r, c):
return 0 <= r < SIZE and 0 <= c < SIZE
def _is_empty(r, c, bd):
return bd[r][c] == 0
def _yield_moves(d, r, c, bd):
for dr, dc in DELTAS:
nr = r + dr
nc = c + dc
if not _is_in_range(nr, nc):
continue
yield(d+1, nr, nc)
while _is_empty(nr, nc, bd) and _is_in_range(nr+dr, nc+dc):
nr = nr + dr
nc = nc + dc
yield(d+1, nr, nc)
def go(r, c, nr, nc, bd):
q = dq()
q.append((0, r, c))
visited = set()
while q:
d, r, c = q.popleft()
if (r, c) == (nr, nc):
return d
if (d, r, c) not in visited:
visited.add((d, r, c))
for next_cursor in _yield_moves(d, r, c, bd):
q.append(next_cursor)
return 0
cand = []
for i, arr in enumerate(board):
for j, val in enumerate(arr):
if val != 0:
cand.append((val, i, j))
cand = sorted(cand)
l = len(cand)//2
used = [0] * l
def back(chosen, x, y, board, moves):
nonlocal answer, used, l
if len(chosen) == l:
answer = min(answer, moves+2*l)
return
for i in range(l):
if not used[i]:
chosen.append(cand[i])
used[i] = 1
nx, ny = cand[2*i][1], cand[2*i][2]
mx, my = cand[2*i+1][1], cand[2*i+1][2]
tmp = deepcopy(board)
n = go(x, y, nx, ny, tmp)
board[nx][ny] = 0
n += go(nx, ny, mx, my, board)
board = deepcopy(tmp)
m = go(x, y, mx, my, board)
board[mx][my] = 0
m += go(mx, my, nx, ny, board)
board[nx][ny] = 0
back(chosen, nx, ny, board, moves+m)
back(chosen, mx, my, board, moves+n)
board = deepcopy(tmp)
used[i] = 0
chosen.pop()
return
back([], r, c, board, 0)
return answerdeepcopy를 쓴 버전 / AA BB CC 를 두개씩 묶어서 계산 / go함수(bfs)를 deque로 구현
from collections import deque as dq
def solution(board, r, c):
answer = 10**6
SIZE = 4
DELTAS = ((1, 0), (0, 1), (-1, 0), (0, -1))
def _is_in_range(r, c):
return 0 <= r < SIZE and 0 <= c < SIZE
def _is_empty(r, c, bd):
return bd[r][c] == 0
def _yield_moves(d, r, c, bd):
for dr, dc in DELTAS:
nr = r + dr
nc = c + dc
if not _is_in_range(nr, nc):
continue
yield(d+1, nr, nc)
while _is_empty(nr, nc, bd) and _is_in_range(nr+dr, nc+dc):
nr = nr + dr
nc = nc + dc
yield(d+1, nr, nc)
def go(r, c, nr, nc, bd):
q = dq()
q.append((0, r, c))
visited = set()
while q:
d, r, c = q.popleft()
if (r, c) == (nr, nc):
return d
if (d, r, c) not in visited:
visited.add((d, r, c))
for next_cursor in _yield_moves(d, r, c, bd):
q.append(next_cursor)
return 0
cand = []
for i, arr in enumerate(board):
for j, val in enumerate(arr):
if val != 0:
cand.append((val, i, j))
l = len(cand)
used = [0] * l
def back(chosen, x, y, board, moves):
nonlocal answer, used, l
if len(chosen) == l:
answer = min(answer, moves+l)
return
for i in range(l):
if not used[i]:
if len(chosen)%2 ==0 or (chosen and chosen[-1][0] == cand[i][0]):
chosen.append(cand[i])
used[i] = 1
nx, ny = cand[i][1], cand[i][2]
n = go(x, y, nx, ny, board)
t1 = board[nx][ny]
board[nx][ny] = 0
back(chosen, nx, ny, board, moves+n)
board[nx][ny] = t1
used[i] = 0
chosen.pop()
return
back([], r, c, board, 0)
return answerdeepcopy 안 쓴 버전 / AABBCC 하나씩 계산 / cand를 정렬안해도 됨 / bfs를 deque로
7. 총평
더럽고 시간제한도 빡빡했고 다시는 만나지 말자
'코딩테스트' 카테고리의 다른 글
| 2020 카카오 인턴십: 경주로 건설 (프로그래머스) (0) | 2021.02.15 |
|---|---|
| 2021 KAKAO BLIND : 합승 택시 요금 (프로그래머스) (0) | 2021.02.15 |
| 2021 KAKAO BLIND : 메뉴 리뉴얼 (프로그래머스) (0) | 2021.02.05 |