[프로그래머스] [1차] 프렌즈4블록 (파이썬 풀이)

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

코딩테스트 연습 - [1차] 프렌즈4블록

 

* 풀이 못 함

def solution(m, n, board):
    ans, board = 0, [list(b) for b in board]
    while True:
        popped = False
        temp = set()
        # 순차 탐색하며 지워지는 블록들의 인덱스 저장
        for i in range(m - 1):
            for j in range(n - 1):
                if board[i][j] != 0 and \
                board[i][j] == board[i + 1][j] == board[i][j + 1] == board[i + 1][j + 1]:
                    temp.update([(i, j), (i + 1, j), (i, j + 1), (i + 1, j + 1)])
                    popped = True
                    
        # 지워진 블록이 없다면 반복문 탈출            
        if popped == False:
            break
		
        # 지워지는 블록 0으로 처리하면서 정답 갱신
        for i, j in list(temp):
            board[i][j] = 0
            ans += 1
        
        for i in range(m)[::-1]:
            for j in range(n):
                # 밑부터 탐색, i는 최초로 0이 나오는 인덱스, x는 그 이후 최초로 문자 나오는 인덱스
                if board[i][j] == 0:
                    x = i - 1
                    while x >= 0 and board[x][j] == 0:
                        x -= 1
                    # 떨어질 블록이 없는 경우
                    if x < 0:
                        board[i][j] = 0
                    # 떨어질 블록이 있는 경우    
                    else :
                        board[i][j], board[x][j] = board[x][j], 0

    return ans

• 아이디어: 재귀적으로 순차탐색하며 지워지는 블록들의 인덱스를 0으로 바꾸면서 정답에 더하고, 0으로 다 처리한 후 떨어질 블록들 처리
• 블록들을 떨어트리는 구현을 못함

* 참고

# board의 행과 열 바꾸기
board = list(map(list, zip(*board)))

* 행과 열 바꾸어 블록 떨어트린 풀이:

def solution(m, n, board):
    ans, board = 0, list(map(list, zip(*board)))
    while True:
        popped = False
        temp = set()
        # 순차 탐색하며 지워지는 블록들의 인덱스 저장
        for i in range(n - 1):
            for j in range(m - 1):
                if board[i][j] != '0' and \
                board[i][j] == board[i + 1][j] == board[i][j + 1] == board[i + 1][j + 1]:
                    temp.update([(i, j), (i + 1, j), (i, j + 1), (i + 1, j + 1)])
                    popped = True
                    
        # 지워진 블록이 없다면 반복문 탈출            
        if popped == False:
            break
		
        # 지워지는 블록 '0'으로 처리하면서 정답 갱신
        for i, j in list(temp):
            board[i][j] = '0'
            ans += 1
        
        new_board = []
        for row in range(n):
            temp = ''
            for col in range(m):
                if board[row][col] != '0':
                    temp += board[row][col]
            new_board.append(list(temp.zfill(m)))
        board = new_board
        
    return ans

• 행과 열 바꾸어서 밑으로 떨어지는 대신 오른쪽으로 밀린다고 생각한 풀이
• 미미하지만 조금더 짧고, 공간 복잡도는 더 안 좋지만, 시간 효율이 훨씬 좋음