[알고리즘] 2018 KAKAO BLIND RECRUITMENT - [1차] 프렌즈4블록

2018 KAKAO BLIND RECRUITMENT - [1차] 프렌즈4블록

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

꽤나 시간이 걸렸던 문제. 2차열 배열 관련 문제가 나오면 지레 겁을 먹는다. 2차원 배열을 조만간 따로 연습해봐야겠다.

• 나의 풀이

  def solution(m, n, board):
      deleted_count = 0
      my_board = make_board(board)
  
      while True:
          candidates_set = set()
  
          # 겹치는 부분 찾기 
          for i in range(1, m):
              for j in range(1, n):
                  if is_square(my_board, i, j):
                      candidates_set = add_candidate(candidates_set, i, j)
          # 겹치는 블록 개수 == 삭제된 블록 개수           
          deleted_count += len(candidates_set)
          # 겹치는 블록 없을 경우 탈출
          if not candidates_set:
              break
          # 겹치는 블록 제거 및 판(board) 조정
          delete_candidates_set(my_board, candidates_set)
          arrange_board(my_board, m, n)
  
      return deleted_count
  
  # 만일 블록이 공백인 board[i][j](블록이 제거된 상태)를 만난다면, 
  # 해당 j열 내에서 다음에 내려올 블록을 찾아 board[i][j]로 이동시킨다.
  def arrange_board(board, m, n):    
      for i in range(m-1, -1, -1):
          for j in range(0, n):
              if board[i][j] == " ":
                  col = [row[j] for row in board]
                  idx = find_next_block_idx(col, i)
                  if idx != -1:
                      board[i][j] = col[idx]
                      board[idx][j] = " "
  
  def find_next_block_idx(arr, start):
      for i in range(start, -1, -1):
          if arr[i] != ' ':
              return i
      return -1
  
  def delete_candidates_set(board, candidates_set):
      for x, y in candidates_set:
          board[x][y] = " "
  
  def add_candidate(candidates_set, i, j):
      candidates_set.add((i-1, j-1)) # 대각선
      candidates_set.add((i-1, j))   # 위
      candidates_set.add((i, j-1))   # 왼쪽
      candidates_set.add((i, j))     
      return candidates_set
  
  def is_square(board, i, j):
      if board[i-1][j-1] == board[i-1][j] == board[i][j-1] == board[i][j] != " ":
          return True
      return False
  
  def make_board(board):
      my_board = []
      for row in board:
          my_board.append(list(row))
      return my_board

• 찾아본 코드 중에 제일 깔끔한 코드

  def solution(m, n, board):
      MAP, to_remove = [[0] * m for _ in range(n)], set()
  
      # * rotate 90'
      for i in range(n):
          for j in range(m):
              MAP[i][j] = board[m-1-j][i]
  
      def search():
          for y in range(n-1):
              for x in range(m-1):
                  if MAP[y][x] == MAP[y+1][x] == MAP[y][x+1] == MAP[y+1][x+1] != ' ':
                      to_remove.update([(y, x), (y+1, x), (y, x+1), (y+1, x+1)])
  
      search()
      while to_remove:
          # * remove the blocks
          while to_remove:
              y, x = to_remove.pop()
              MAP[y][x] = ' '
  
          # * trim
          for idx, row in enumerate(MAP):
              row_str = "".join(row).replace(' ', '')
              row_str += ' ' * (m - len(row_str))
              MAP[idx] = list(row_str)
  
          search()
  
      return sum(map(lambda x: x.count(' '), MAP))
  
  if __name__ == "__main__":
      m, n, board = 4, 5, ["CCBDE", "AAADE", "AAABF", "CCBBF"]
      # m, n, board = 6, 6, ["TTTANT", "RRFACC",
      #                      "RRRFCC", "TRRRAA", "TTMMMF", "TMMTTJ"]
      print(solution(m, n, board))