사용자 도구

사이트 도구


ps:problems:programmers:42894

블록 게임

ps
링크https://programmers.co.kr/learn/courses/30/lessons/42894
출처프로그래머스
문제 번호42894
문제명블록 게임
레벨Level 4
분류

구현

시간복잡도O(n^2)
인풋사이즈n<=50
사용한 언어Python
해결날짜2020/12/27

풀이

  • 그냥 구현문제. 어떻게든 돌아가게 만드는 것은 어렵지 않지만, 깔끔하게 짜려면 (귀찮은) 시간이 소요된다..
  • 처음에 실수했던 부분은, 어떤 블록을 제거할 수 있는지의 여부를 그 블록 위에 다른 블록이 존재하는가로 체크했더니, 이런 예외 케이스에 부딪혔다
    • 11
      12
      12 
       22
      • (2 위에 1이 있지만, 2는 지울 수 있다)
  • 그래서 로직을 다르게 바꿔서 작성했다. 보드 전체에 대해서 한번의 스캔으로 계산을 마치므로 시간복잡도는 O(|board|) = O(N^2)이다

코드

"""Solution code for "Programmers 42894. 블록 게임".

- Problem link: https://programmers.co.kr/learn/courses/30/lessons/42894
- Solution link: http://www.teferi.net/ps/problems/programmers/42894
"""

import collections
import operator

EMPTY = 0
BLACK = -1


def can_remove(block, block_coords, board):
    if len(block_coords) != 4:
        return False
    r1 = min(block_coords, key=operator.itemgetter(0))[0]
    r2 = max(block_coords, key=operator.itemgetter(0))[0]
    c1 = min(block_coords, key=operator.itemgetter(1))[1]
    c2 = max(block_coords, key=operator.itemgetter(1))[1]
    for r in range(r1, r2 + 1):
        if any(x not in (BLACK, block) for x in board[r][c1:c2 + 1]):
            return False
    return True


def fill_black(board, r, c):
    board[r][c] = (BLACK if r == 0 or board[r - 1][c] == BLACK else EMPTY)


def solution(board):
    N = len(board)
    removed_count = 0
    coords_by_block = collections.defaultdict(list)
    for r in range(N):
        for c in range(N):
            block = board[r][c]
            if block == EMPTY:
                fill_black(board, r, c)
            else:
                block_coords = coords_by_block[block]
                block_coords.append((r, c))
                if not can_remove(block, block_coords, board):
                    continue
                removed_count += 1
                for block_r, block_c in block_coords:
                    fill_black(board, block_r, block_c)

    return removed_count

토론

하민수, 2021/03/04 05:55
`operator` 이런 라이브러리도 있었군요. 기가막힙니다
댓글을 입력하세요:
N᠎ O X X D
 
ps/problems/programmers/42894.txt · 마지막으로 수정됨: 2021/01/21 15:23 저자 teferi