https://programmers.co.kr/learn/courses/30/lessons/42894#
-
flow
문제를 읽고 처음 떠오른 아이디어는 12가지 블록중에 5가지 경우를 제외한 나머지는 어떠한 경우에도 속이 꽉 채워진 직사각형을 만들 수 없다는 것을 깨달았다. 이 때 5가지의 공통점은 (ㅏ) 모양과 (ㅓ) 모양을 제외하고 위에서 부터 볼 때, 가장 윗줄 블록이 하나인 경우 인 것을 알 수 있고, 위에서 부터 차례대로 반복문 돌려 나아가면 풀 수 있겠다는 생각이 들었다. 이 때 주의해야 할 점은, 없앨 수 없는 블록을 찾았을 때, 그 블록이 있는 열에는 더 이상 검은 블록을 더 아래로 쌓을 수 없으므로 체크해줘야 되는 점(코드에서 able list)과, 한 번 확인이 된 블록은 표시를 없애든지 visit list에 고유번호를 넣어두고 관리하든지 해야 효율적인 코드가 나온다. 결과적으로 없앨 수 있는 5가지 경우일 때, 없앨 때 채워넣어야 할 공간이 비어 있는 지 확인하고, 거기가 able list에서 쌓을 수 있는 공간인지 판단도 되면 그 블록은 없앨 수 있다고 보면 된다.
마지막으로 반례를 계속 생각하다 보니 찾은 경우가, [[1, 2, 0, 0], [1, 2, 2, 2], [1, 1, 0, 0]], 와 [[0, 2, 0, 1], [2, 2, 2, 1], [0, 0, 1, 1]] 이런 식으로 가장 윗줄이 같은 블록인데 오른쪽에 있는 블록을 먼저 지우면 두 블록 다 지워지는 경우가 있다. (내 반복문은 위에서부터 왼쪽부터 시작되기 때문에 이 경우 따로 처리를 해줘야 올바른 정답이 된다.)
시간 복잡도는 O(N^2) 반복문이 된다. -
result
https://github.com/songjy6565/alg-py/blob/master/programmers/level4/A42894.py
