공부하고 기록하는, 경제학과 출신 개발자의 노트

프로그래밍/코딩테스트 문제풀이

[Python] 프로그래머스. 2019 카카오 recruit - 블록 게임 (Level 4)

inspirit941 2020. 5. 19. 19:28
반응형

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

 

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

[[0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,4,0,0,0],[0,0,0,0,0,4,4,0,0,0],[0,0,0,0,3,0,4,0,0,0],[0,0,0,2,3,0,0,0,5,5],[1,2,2,2,3,3,0,0,0,5],[1,1,1,0,0,0,0,0,0,5]] 2

programmers.co.kr

구현까지 시간이 오래 걸렸던 문제.

검은 블록을 채울 수 있는 모든 공간에 검은 블록을 채우고,

검은 블록과 설치된 블록을 합쳤을 때 직사각형 블록이 나올 수 있는지를 검사한다.

 

특징이라면, 제거 가능한 직사각형 블록이 되기 위해서는

직사각형 밑변에 해당하는 부분은 반드시 설치된 블록이어야 한다는 것.

그러므로, 배열 가장 아래에서부터 순회하며 '설치된 블록'의 길이가 2 또는 3일 경우 직사각형 블록 여부를 검사하는 식으로 해결했다.

 

 

# 블록이 직사각형인지
def check_shape(start, color, row_num, board):
y, x = start
color = board[y][x]
coord = set()
color_cnt, black_cnt = 0, 0
if row_num == 2 and y - 2 >= 0:
# [1,#],
# [1,#],
# [1,1] 와 같은 형태
for cx in range(x, x-2, -1):
for cy in range(y, y-3, -1):
if cy >= 0 and (board[cy][cx] == color or board[cy][cx] == '#'):
if board[cy][cx] == color: color_cnt += 1
if board[cy][cx] == '#': black_cnt += 1
coord.add((cy, cx))
else:
return None
if color_cnt == 4 and black_cnt == 2:
return coord
else:
return None
# [1,0,0],
# [1,1,1] 와 같은 형태
if row_num == 3 and y-1 >= 0:
for cx in range(x, x-3, -1):
for cy in range(y, y-2, -1):
if cy >= 0 and (board[cy][cx] == color or board[cy][cx] == '#'):
if board[cy][cx] == color: color_cnt += 1
if board[cy][cx] == '#': black_cnt += 1
coord.add((cy, cx))
else:
return None
# 블록 개수 4개, 검은 블록 2개일 경우에만 제거 가능.
if color_cnt == 4 and black_cnt == 2:
return coord
else:
return None
return None
# 검은 블록을 채워넣는 함수
def build(board):
for x in range(len(board[0])):
for y in range(len(board)):
if board[y][x] == '#':
continue
if board[y][x] == 0:
board[y][x] = '#'
elif board[y][x] != 0:
break
# 전체 배열을 순회하면서, 직사각형 조건에 맞는지 확인하는 함수
def search_shape(board):
for y in range(len(board)-1, -1, -1):
consecutive = 0
color = None
for x in range(len(board[0])):
# 빈 공간일 경우
if board[y][x] == 0:
color = None
consecutive = 0
continue
# 검은 블록을 # 로 설정했기 때문에, type()이 int이면서 0이 아닌 블록 = 설치된 블록
if type(board[y][x]) is int and board[y][x] != 0:
if color == None:
consecutive = 1
color = board[y][x]
continue
if board[y][x] != color:
color = board[y][x]
consecutive = 1
continue
if color == board[y][x]:
consecutive += 1
# 가로
if 2 <= consecutive <= 3:
coord = check_shape((y,x), color, consecutive, board)
if coord is not None:
return coord
return None
# 블록 제거
def remove(board, coord):
for y, x in coord:
board[y][x] = 0
def solution(board):
cnt = 0
while True:
# 1. 조건상 채울 수 있는 모든 공간에 검은 블록 채워넣기
build(board)
# 2. 검은 블록 + 블록으로 제거될 수 있는 블록 찾기
coord = search_shape(board)
# 찾을 수 없는 경우 break
if coord is None:
break
# 제거 블록개수 + 1
cnt += 1
# 블록 제거하기
remove(board, coord)
return cnt
반응형