[1차] 프렌즈4블록 with Python

 

문제 출처: (프로그래머스 코딩테스트 연습) https://www.programmers.co.kr/learn/courses/30/lessons/17679

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

2018 KAKAO BLIND RECRUITEMENT [1차] 프렌즈4블록 (LEVEL 2)

 

1. 알고리즘

• 모든 칸(n-1칸을 m-1번)을 돌며 기준칸(x, y)을 비롯한 4개의 칸((x, y), (x+1, y), (x+1, y), (x+1, y+1))의 값을 확인
  • 4개 칸의 값이 일치할 경우 삭제 블록 리스트(erase_board)에 좌표를 추가
• 삭제 블록 리스트를 집합 자료형으로 만들어 중복 칸 제거
• 삭제 블록을 행, 열로 정렬하여 순서대로 없애고 위의 칸을 내려줌
  • 0번째 행이면 0을 추가
  • 그 외의 행(r)이면, 반복문을 사용하여 해당 열의 한 줄 위 데이터(r-1, c)를 내려줌. 0번째 행에 도달하면 0을 추가
  • 블록 값 갱신
• 블록 갯수 반환

 

2. 유의사항

 

3. 어려웠던 점, 해결방법

• 리스트를 갱신할 때, 열을 갱신해야하는데 행을 갱신하는 것으로 착각하여 코드를 작성했음. 열을 갱신하도록 수정, 해결
• 0번째 행일 때의 처리를 반복문으로 해당 행과 0번 행만을 처리하여 5, 6, 10번 테스트케이스 오류 발생
  • 반복문에서 0번 행 처리를 해주지 않았더니 5, 6, 10, 11번 테스트케이스 오류 발생
  • 반복문으로 해당 행부터 0번으로 해당 열 데이터를 한 줄씩 내려주도록 하여 해결.

 

4. 소스코드

상세 코드 설명은 주석

#4블록 확인 함수
def check_board(x, y, board):
    #확인할 좌표
    filter = [(x, y+1), (x+1, y), (x+1, y+1)]
    #기준 좌표의 블록 값
    value = board[x][y]
    
    for _x, _y in filter:
        #만약 일치하지 않는 경우 False 반환
        if value != board[_x][_y]:
            return False
    
    #모두 일치한 경우 True 반환
    return True
 
 
def solution(m, n, board):
    #삭제 블록 갯수 변수
    answer = 0
    
    while True:
        #삭제 블록 집합, set자료형으로 중복 좌표 제거
        erase_board = set()
        #블록 확인
        for r in range(m-1):
            for c in range(n-1):
                #'0'은 비워진 블록
                if board[r][c] == '0':
                    continue
                
                #4블록 확인, 같은 블록 4개이면
                if check_board(r, c, board):
                    #삭제 블록 집합에 해당 좌표 추가
                    erase_board.update(
                        [(r, c), (r+1, c), (r, c+1), (r+1, c+1)])
        
        
        #삭제할 블록이 존재하지 않으면 while 반복문 종료
        if not erase_board:
            break
        
        #삭제 블록 집 (행, 열)로 정렬하여 순서대로 없애줌
        for x, y in sorted(erase_board, key=lambda x: (x[0], x[1])):
            #0행일 때, 해당 위치 값을 '0'으로 대체
            if x == 0:
                board[x] = board[x][:y]+'0'+board[x][y+1:]
            else:
                #반복문으로 위치한 행부터 한 줄 위씩 0행까지 반복
                for r in range(x, -1, -1):
                    #0행일 때 '0'값 대체
                    if r == 0:
                        board[0] = board[0][:y]+'0'+board[0][y+1:]
                    #0행이 아닐 때, 한 줄 위의 값으로 현재 위치 값 대체
                    else:
                        board[r] = board[r][:y]+board[r-1][y]+board[r][y+1:]
            
            #삭제 블록 갯수 카운팅
            answer += 1
            
    return answer

 

5. 고민

• 정렬을 꼭 해야했나? ▶ 정렬 제거 시 오류가 발생함. 정렬을 하지 않으려면 아예 코드를 변경해야할 듯
• 그냥 erase_board데이터를 set자료형으로 쭉 진행했어도 되지않나? ▶ 된다. 4번 소스코드 업데이트함.
• 블록을 없애고, 위의 블록을 내리는 연산에서 board를 전치해서 행연산으로 처리했으면 더 간편하지 않았을까? 아니면 0으로 값을 대체하고, 한 번에 지우고...할 수 있지 않을까?