[프로그래머스][KAKAO_BLIND][2019] 블록 게임

프로그래머스 코딩테스트 고득점 Kit의 문제입니다.

https://programmers.co.kr/learn/challenges?tab=algorithm_practice_kit

코딩테스트 연습

 

문제

https://programmers.co.kr/learn/courses/30/lessons/42894

코딩테스트 연습 - 블록 게임

 

내가 작성한 코드

def candidates(board, i, j, v, N):
    # 아래 오른쪽 왼쪽
    # (1,0), (0,1), (0,-1)
    def check_shape(board, i, j, v, N, dir):
        shape = []
        nw_i, nw_j = i, j
        for d_i, d_j in dir:
            nw_i += d_i
            nw_j += d_j
            if not(0 <= nw_i < N and 0 <= nw_j < N and board[nw_i][nw_j] == v):
                return []
            shape.append((nw_i, nw_j))
        return shape

    dir = [(1,0), (0,1), (0,1)]
    shape = check_shape(board, i, j, v, N, dir)
    if shape:
        return [(i, j)]+shape,[(i, j+1), (i,j+2)]

    dir = [(1, 0), (1, 0), (0,-1)]
    shape = check_shape(board, i, j, v, N, dir)
    if shape:
        return [(i, j)]+shape,[(i+1, j - 1), (i, j-1)]

    dir = [(1, 0), (1, 0), (0, 1)]
    shape = check_shape(board, i, j, v, N, dir)
    if shape:
        return [(i, j)]+shape,[(i+1, j + 1), (i, j + 1)]

    dir = [(1, 0), (0, -1), (0, -1)]
    shape = check_shape(board, i, j, v, N, dir)
    if shape:
        return [(i, j)]+shape,[(i, j - 1), (i, j - 2)]

    dir = [(1, 0), (0, -1), (0, 2)]
    shape = check_shape(board, i, j, v, N, dir)
    if shape:
        return [(i, j)]+shape,[(i, j - 1), (i, j +1)]
    return None

def drop_and_match(board,  to_check):
    for r, c in to_check:
        i, j = 0, c
        while i <= r:
            if board[i][j] != 0:
                return False
            i+=1
    return True

def remove_block(board, shape):
    for i, j in shape:
        board[i][j] = 0

def solution(board):
    answer = 0
    N = len(board)
    keep = []
    for i in range(N):
        for j in range(N):
            if board[i][j] != 0:
                if candidates(board, i, j, board[i][j], N):
                    keep.append(candidates(board, i, j, board[i][j], N))
                    for shape, to_check in keep[::-1]:
                        if drop_and_match(board, to_check):
                            remove_block(board, shape)
                            keep.remove((shape, to_check))
                            answer += 1

    return answer

• 문제 조건 축소
  
  • 블록의 종류는 총 12개
  • 이 중 제거 가능한 종류는 총 5개로, 해당하지 않은 블록은 무시
  • 이 블록에서도 board를 (0, 0)부터 (N, N)까지 순차 탐색할 경우, 만나는 블록은 항상 같다
  • 해당 블록을 기준으로 제거 가능한 종류 5가지를 정의
• 문제 조건
  • 블록 중 다른 블록이 제거되야 제거할 수 있는 블록이 존재
  • 따라서, 제거 가능한 종류의 블록이 제거되지 않았을 경우 정보를 저장
  • 다른 블록이 제거되었을 때 다시 제거 가능한지 확인

 

다른 사람이 작성한 코드

None

 

기억해야할 것

• 조건을 따져보는데에 시간이 걸리지만, 다른 복잡한 문제에 비해서는 비교적 시간이 덜 걸린 문제였다