카카오 코딩테스트 - 프렌즈4블록

string은 immutable 하므로 배열처럼 str[3] = 's' 이렇게 assign 해줄 수 없다.

그래서 입력 값을 board[i] = list(board[i]) 로 ['s','t','r'] 형태로 바꿔줬다.

한 블록이 여러 2x2에 해당될 수 있으므로 중복 처리를 위해 한 턴 체크를 할 때 사라지는 블록을 set에 저장했다.

처음에 s = {} 형태로 set도 되는 줄 알고 초기화했는데 무조건 dictionary로 인식하는 것 같다. s = set()로 초기화해야 한다.

블록은 열 단위로 empty 칸을 보면서 처리했는데, board[m-1][j]부터 1씩 빼면서, 즉 보드의 바닥부터 체크했다.

그러면 o(m) 으로 해결할 수 있는데, 빈 칸이면 카운트를 세고, 빈칸이 아니면 이때까지 나온 빈 칸 만큼 밑으로 옮겨주면 되기 때문이다. 왼쪽 위가 (0,0), 오른쪽 밑이 (M-1, N-1) 이기 때문에 '빈칸만큼 밑으로 옮기기'를 board[i+empty_cnt][j] = board[i][j] 로 처리해야 지금 보고 있는 칸을 밑으로 옮겨주는건데, i+empty를 i-empty로 쓰는 바람에 헤맸다. board의 방향이 일반적인 0 -> N, 0->M이 아닐 시에는 꼭 한 번 더 생각하고 체크해야겠다. 그리고 보통 높이가 N, 폭이 M으로 표현되는 경우가 많은데 여기서는 반대라서 중간중간 헷갈렸던 것 같다. 자주 본다고 머릿속으로 내정해놓지 말고 그 때 그 때 요구사항대로 머리를 업데이트할 줄 알아야겠다.

def print_board(m, n, board):
    for i in range(m):
        for j in range(n):
            print(board[i][j], end=" ")
        print()

def checker(x, y, board):
    t = board[x][y]
    if t.islower(): return False
    if board[x+1][y] == t and board[x][y+1] == t and board[x+1][y+1] == t:
        return True
    else:
        return False

def solution(m, n, board):
    for i in range(m):
        board[i] = list(board[i])

    answer = 0
    to_erase = set()
    #print("origin")
    #print_board(m,n,board)
    while True:
        for i in range(m-1):
            for j in range(n-1):
                if checker(i,j,board):
                    to_erase.update([(i,j), (i+1,j),(i, j+1), (i+1, j+1)])
        #print(to_erase)

        for (x,y) in to_erase:
            answer += 1
            board[x][y] = 'q'


        #print("after qq")
        #print_board(m,n,board)

        for j in range(n):
            empty_cnt = 0
            for i in range(m-1, -1, -1):
                #print("i: ", i," empty_cnt: ", empty_cnt)
                if board[i][j] == 'q':
                    empty_cnt += 1
                elif empty_cnt != 0:
                    board[i+empty_cnt][j] = board[i][j]
                    board[i][j] = 't'

        #print("after push:")
        #print_board(m,n,board)
        if len(to_erase) == 0:
            break
        to_erase = set()


    return answer