[프로그래머스] 2019 카카오 블라인드 - 블록 게임

문제

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

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

---

풀이

약간 카카오는

설마 이렇게까지 구현하는 문제일까??

내가 멍청해서 깔끔한 풀이를 생각하지 못하는건 아닐까?

라는 생각을 들게 하는 문제를 내는 것 같다..

 

https://tech.kakao.com/2018/09/21/kakao-blind-recruitment-for2019-round-1/

2019 카카오 신입 공채 1차 코딩 테스트 문제 해설

해설을 보니 정말 시키는대로 구현하는 문제였다.

다만 약간의 아이디어가 필요한 것 같다.

나의 경우 이 블록을 지울 수 있는지 판단하는 부분에서 막혔었다. 해당 블록 위의 보드가 다른 블록으로 막혀있는지를 확인했어야 했다.

내가 생각한 풀이는 두번째 풀이와 가까워 그대로 구현했다.

blocks = {
    1: [[(0, 0), (0, 1), (1, 1), (2, 1)], (0, 2)],
    2: [[(0, 0), (0, 1), (0, 2), (-1, 2)], (-1, 0)],
    3: [[(0, 0), (0, 1), (0, 2), (1, 2)], (0, 1)],
    4: [[(0, 0), (0, 1), (-1, 1), (-2, 1)], (-2, 0)],
    5: [[(0, 0), (-1, 1), (0, 1), (1, 1)], (-1, 1)],
}

def solution(board):
    answer = 0
    n = len(board)
    
    def getBlock(r, c, number):
        for b, d in blocks.items():
            #print(b, d)
            flag = True
            for x, y in d[0]:
                try:
                    if board[r+y][c+x] != number:
                        flag = False
                        break
                except:
                    flag = False
                    break
            if flag:
                return [b, d]
        return [-1, -1]
    
    for i in range(n):
        for j in range(n):
            if board[i][j] == 0:
                continue
            b, d = getBlock(i, j, board[i][j])
            if b > 0: #지울 수 있는 블록임
                #위에 블록이 있는지(막혀있는지)
                isErasable = True
                for c in range(d[1][0],d[1][1]+1):
                    for r in range(i):
                        if board[r][j+c] != 0:
                            isErasable = False
                if isErasable:
                    #위에 블록이 없다면 지우기
                    answer += 1
                    for x, y in d[0]:
                        board[i+y][j+x] = 0
        
    print('----------------------')
    print(*board, sep="\n")
            
    return answer

 

그런데 30점을 받았다..

질문하기를 찾아보고 스스로 복기해보면서 세가지의 예외를 찾았다.

 

1.  y 축 기준으로 0부터 i-1까지, 즉 블록의 가장 윗부분에서부터 보드 가장 위까지를 검사했었다. 그러나 L과 같은 모양의 블록에서는 i+2의 부분까지 검사를 해야 한다. (오목하게 파인 부분 위에도 블록이 있는지 검사해야 하기 때문)

 

2. L과 같은 블록의 모양에서는 오목한 부분 위의 부분만 체크해야 한다. 그러니 L의 I 부분(모양으로 봤을때 길쭉한 부분)의 위쪽에는 블록이 있어도 된다. -> 한마디로 검은색 블록이 채워져야 할 부분에 대한 정의가 잘못되었었다.

 

3. 다음과 같은 경우의 수를 고려해야 한다. 나는 왼쪽에서 오른쪽으로 검사하기 때문에 오른쪽 블록을 먼저 제거하면 왼쪽의 블록을 제거할 수 있는 예외가 있다.

위의 예외를 생각해 코드를 수정했다.

blocks = {
    1: [[(0, 0), (0, 1), (1, 1), (2, 1)], [(1, 2), (0, 1)]],
    2: [[(0, 0), (0, 1), (0, 2), (-1, 2)], [(-1, -1), (0, 2)]],
    3: [[(0, 0), (0, 1), (0, 2), (1, 2)], [(1, 1), (0, 2)]],
    4: [[(0, 0), (0, 1), (-1, 1), (-2, 1)], [(-2, -1), (0, 1)]],
    5: [[(0, 0), (-1, 1), (0, 1), (1, 1)], [(-1, 1), (0, 1)]],
}

def solution(board):
    answer = 0
    n = len(board)
    
    def getBlock(r, c, number):
        for b, d in blocks.items():
            flag = True
            for x, y in d[0]:
                try:
                    if board[r+y][c+x] != number:
                        flag = False
                        break
                except:
                    flag = False
                    break
            if flag:
                return [b, d]
        return [-1, -1]
    
    i = 0
    while i<n:
        for j in range(n):
            if board[i][j] == 0:
                continue
            b, d = getBlock(i, j, board[i][j])
            if b > 0: #지울 수 있는 블록임
                #위에 블록이 있는지(막혀있는지)
                isErasable = True
                for c in range(d[1][0][0],d[1][0][1]+1):
                    for r in range(i + d[1][1][1]):
                        if board[r][j+c] != 0 and board[r][j+c] != board[i][j]:
                            isErasable = False
                if isErasable:
                    #위에 블록이 없다면 지우기
                    answer += 1
                    for x, y in d[0]:
                        board[i+y][j+x] = 0
                    #오른쪽 블록이 삭제되었을 때 왼쪽 블럭을 삭제하는 경우의 수를 위해
                    i -= 1
        i += 1
  
    return answer

통과!

 

---

다른 사람의 풀이

 

import numpy as np
def solution(board):
    answer = 0

    blocks = {}
    for i, row in enumerate(board):
        for j, col in enumerate(row):
            if col > 0:
                if col not in blocks:
                    blocks[col] = {"left": 51, "right": -1, "top": 51, "bottom" : -1, "coords" : []}
                blocks[col]["left"] = min(blocks[col]["left"], j)
                blocks[col]["right"] = max(blocks[col]["right"], j)
                blocks[col]["top"] = min(blocks[col]["top"], i)
                blocks[col]["bottom"] = max(blocks[col]["bottom"], i)
                blocks[col]["coords"].append([i, j])

    board = np.array(board)

    removed = 1
    while removed > 0:
        removed = 0
        for block_key in blocks:
            can_remove = True
            block = blocks[block_key]
            zeros = 0
            for i in range(block["top"], block["bottom"]+1):
                for j in range(block["left"], block["right"]+1):
                    if board[i][j] == 0:
                        zeros+=1
                        if (board[:i,j] > 0).any():
                            can_remove = False
                            break
                if not can_remove:
                    break
            if can_remove and zeros == 2:
                for coord in blocks[block_key]["coords"]:
                    board[coord[0]][coord[1]] = 0
                del blocks[block_key]

                removed += 1
                answer += 1
                break


    return answer