프로그래머스 코딩테스트 고득점 Kit의 문제입니다.
https://programmers.co.kr/learn/challenges?tab=algorithm_practice_kit
코딩테스트 연습
기초부터 차근차근, 직접 코드를 작성해 보세요.
programmers.co.kr
문제
https://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
내가 작성한 코드
import sys
from itertools import permutations
from collections import defaultdict, deque
dir = [(0,1),(0,-1),(1,0),(-1,0)]
def make_nums(board):
nums = defaultdict(list)
for i in range(4):
for j in range(4):
if board[i][j] != 0:
nums[board[i][j]].append((i, j))
return nums
def get_cost(r1, c1, r2, c2, board):
q = deque([(0, r1, c1)])
while q:
cost, r, c = q.popleft()
if r == r2 and c == c2:
return cost + 1
for d in dir:
nw_r = r+d[0]
nw_c = c+d[1]
if 0 <= nw_r < 4 and 0 <= nw_c < 4:
q.append((cost+1, nw_r, nw_c))
for d in dir:
nw_r = r+d[0]
nw_c = c+d[1]
while 0 <= nw_r < 4 and 0 <= nw_c < 4 and board[nw_r][nw_c] == 0:
nw_r += d[0]
nw_c += d[1]
if not(0 <= nw_r < 4 and 0 <= nw_c < 4):
nw_r -= d[0]
nw_c -= d[1]
q.append((cost+1, nw_r, nw_c))
return -1
def get_all_cost(order, nums, board, r, c, memo):
if not order:
return 0
card = order[0]
first_r, first_c = nums[card][0][0], nums[card][0][1]
second_r, second_c = nums[card][1][0], nums[card][1][1]
key = tuple(map(tuple, board)) + (r, c, card, 1)
if memo[key] != 0:
to_first_cost = memo[key]
board[first_r][first_c] = 0
board[second_r][second_c] = 0
else:
to_first_cost = get_cost(r, c, first_r, first_c, board)
board[first_r][first_c] = 0
to_first_cost += get_cost(first_r, first_c, second_r, second_c,board)
board[second_r][second_c] = 0
memo[key] = to_first_cost
to_first_cost += get_all_cost(order[1:], nums, board, second_r, second_c, memo)
board[first_r][first_c] = card
board[second_r][second_c] = card
key = key[:-1] + (r, c, card, 2)
if memo[key] != 0:
to_second_cost = memo[key]
board[second_r][second_c] = 0
board[first_r][first_c] = 0
else:
to_second_cost = get_cost(r, c, second_r, second_c, board)
board[second_r][second_c] = 0
to_second_cost += get_cost(second_r, second_c, first_r, first_c, board)
board[first_r][first_c] = 0
memo[key] = to_second_cost
to_second_cost += get_all_cost(order[1:], nums, board, first_r, first_c, memo)
board[first_r][first_c] = card
board[second_r][second_c] = card
return min(to_first_cost, to_second_cost)
def solution(board, r, c):
answer = sys.maxsize
nums = make_nums(board)
num_order = list(permutations(nums, len(nums)))
memo = defaultdict(int)
for order in num_order:
answer = min(answer, get_all_cost(order, nums, board, r, c, memo))
return answer
- 모든 케이스를 확인해야함
- 카드를 선택하는 순서에 따라 결과가 달라짐
- 같은 숫자의 카드도 두 카드 중 어느 카드부터 선택하는지에 따라 결과가 달라짐
- 고려해야할 것
- 위치를 이동할 때
- 4방향
- ctrl+방향시 카드를 만나면 카드에서 멈추고, 아니면 끝까지 이동 - DP 사용시 key
- 나는 board + 현재 위치(r, c) + 카드 번호 + 첫 번째/두 번째 카드를 사용
- key 선택에 따라서 시간초과 발생
- 첫 번째/두 번째 카드를 반드시 고려해야함!
- 위치를 이동할 때
다른 사람이 작성한 코드
None
기억해야할 것
- 문제에서 데이터의 범위가 작은 경우는 구현이 복잡한 문제인 듯 하다
- grid도 4x4로 고정이고, 카드 종류도 1~6이라 간단해보인다
- 그러나 고려해야할 사항이 많다
- 그만큼 계산량이 많기 때문에, 더더욱 복잡하다
'코딩테스트' 카테고리의 다른 글
[프로그래머스][KAKAO_BLIND][2020] 자물쇠와 열쇠 (0) | 2021.08.29 |
---|---|
[프로그래머스][KAKAO_BLIND][2019] 오픈채팅방 (0) | 2021.08.29 |
[프로그래머스][KAKAO_BLIND][2021] 합승 택시 요금 (0) | 2021.08.25 |
[백준][오픈테스트] 3초 정렬 (0) | 2021.08.24 |
[백준][그래프] 최소 스패닝 트리 (0) | 2021.08.24 |