링크
짝지어 제거하기
난이도
- 중상?
- 2*2가 겹친것을 어떻게 처리하냐에서 오래걸림.
문제 요약
- 2*2가 같으면 삭제되면서 위에있는 요소들이 쌓인다, 삭제된 갯수는?
초반접근
- 같은모양의 2*2가 겹쳐져있는것을 dfs를 이용해 찾으려 했다.
- 오래걸리며, 약간만 커져도 결과가 어마어마하게 커져서 에러가 나온다.
해결법
- 2*2가 같은것들의 좌표를 저장한다.
- 삭제될 좌표들에대해 삭제를 진행한다.
- 2*2로 같은게 없을때 까지 반복한다.
알고리즘 간단 정리
- 삭제할 요소가 없을때까지 배열 반복
- 배열내부 반복
- [x][y]===[x+1][y+1]&&[x][y]===[x][y+1]&&[x][y]===[x+1][y]이면 4개의 좌표를 저장
- 삭제진행
- 삭제좌표에대해 정렬 진행(x좌표 우선 오름차순, y오름차순)
- 중복된것은 제외하면서 좌표에 대해 삭제 처리
- 해당 좌표를기준으로 위로 반복하면서 하나씩 아래로 내린다.
- 삭제진행시 count+1
- count가 삭제된 블록의 갯수가 된다.
후기
- 삭제할 요소를 너무 효율과 알고리즘만 생각하다보니 복잡하게 구현하였다.
- dfs방식으로 결과는 같지만, 속도가 너무 느리고 stack overflow가 나오게 되었다.
- 단순하게 2*2로 보면서 저장하는 방식이 무식해보여도 가장 간단한 방식이었다.
- 겹친것을 너무 집중하니 시야가 좁아졌었다.
- 이걸 시간안에 바로 떠올라야한다.
아이디어