[Python] 프로그래머스 / 2019 KAKAO BLIND RECRUITMENT / 블록 게임

문제 링크

 

와... 이거 어렵고 재밌었다.

 

실전 코테에서 이런 그림이 뜨게 된다면 머릿속에 큰일났다는 생각 말고는 들지 않을 것이다. 하지만 차근차근 하다보면 어렵지 않다.

 

 

일단 위에서 블록을 떨어뜨려서 직사각형을 만들 수 있는 건 위의 다섯 개 밖에 없다. 이들은

1. 첫 번째 줄에 하나, 두 번째 줄에 하나, 세 번째 줄에 두 개
2. 첫 번째 줄에 하나, 세 번째 줄에 세 개

중에 하나이다.

 

풀이 방법

일단 문제에 제시된 예시를 살펴보자.

 

첫 번째로는 우선, Counter를 이용해서 각 행에 적힌 숫자를 세는 것이다.

Counter를 이용하는 이유는 참조를 빠르고 효율적으로 할 수 있기 때문이다. 저 Counter들은 리스트에 저장한다.

 

그 다음으로는, 리스트에 저장된 Counter를 분석한다.

 

맨 위에있는 "가능할 수도 있는 도형"부터, 북쪽을 분석한다. 이때 numpy의 np.where()를 활용하면 좋다.

 

이렇게만 하면 되긴 하는데... 예외 상황이 생각보다 엄청 많아서 코드 작성이 쉽지 않았다. 프로그래머스 질문게시판에서 발견된 여러 예외상황 중, 가장 생각하기 어려웠고 충격적이었던 것은 다음과 같다. 

와... 처음에 이 예외를 봤을 때 머리를 세게 맞는 기분이었다. 이를 위해서, 어느 한 행에 대한 탐색이 완료되면, 그 행에서 나중에 탐색된 애가 먼저 탐색된 애를 방해하는 존재가 아니었는지 검토하는 코드를 넣었다.

 

정답 코드

from collections import Counter
import numpy as np

def solution(board):

    counters = []
    start = False
    for row in board :
        if any(row) :
            start = True

        if start :
            counters.append(Counter(row))

    negligible = set([0])
    seen = set([0])

    N = len(counters)

    board = np.array(board)

    for i in range(N-1) :
        interrupters = dict()

        for num in counters[i].keys() :

            if num in seen:
                continue 
            seen.add(num)

            L_shape = (i < N-2 and counters[i][num] == 1 and counters[i+1][num] == 1 and counters[i+2][num] == 2)
            reverse_T_shape = (i < N-1 and counters[i][num] == 1 and counters[i+1][num] == 3)

            if L_shape or reverse_T_shape :
                positions = np.where(board == num)
                x = max(positions[0])

                flag = True
                
                interrupter = set()
                for y in set(positions[1]) :
                    north = board[:x, y]
                    set_north = set(north)
                    if num in set(north) :
                        continue

                    if not set_north.issubset(negligible) :
                        interrupter |= set(set_north - negligible)
                        flag = False
                
                if flag :
                    negligible.add(num)

                print(num, interrupter)
                if interrupter :
                    interrupters[num] = interrupter

        for num, interrupter in interrupters.items() :
            if interrupter.issubset(negligible) :
                  negligible.add(num)
                    
    return len(negligible) - 1