https://school.programmers.co.kr/learn/courses/30/lessons/17679
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
문제풀이
처음에는 dfs로 풀이를 할까 생각하느라 규칙을 발견하는데 생각보다 시간이 걸렸었다.
- board는 불변한 객체인 문자열로 주어지기 때문에 각 문자열을 리스트로 변환
- 현재 행렬을 기준으로 2 * 2 영역이 전부 동일한 문자일 경우 각 좌표를 집합에 추가
- 집합 자료형은 순서를 보장하지 않기 때문에 행렬을 오름차 정렬
- 인덱스 에러를 방지하기 위해 현재 행렬을 "0"으로 치환, "0"이 윗 행으로 전부 올라갈 때 까지 각 행의 위치를 바꿈
현재 코드상 딱히 deque를 사용할 이유는 없었지만 처음에 접근할 때에는 pop으로 처리할 예정이었기에 좀 더 용이한 deque를 사용하게 되었었다.
집중적으로 풀이를 한다면 특정 영역이 2 * 2인지를 확인 하기 위해서는 가장 먼저 발견되는 캐릭터를 기준으로 삼고 현재 행렬, 현재 행의 오른쪽 열, 다음 행렬, 다음 행의 오른쪽 열이 전부 동일한 문자인지 확인하면 된다.
반복문을 진행하면서 매개체를 수정하게 된다면 인덱스 오류가 나기 때문에 집합에 각 좌표를 저장한다. 집합을 사용하는 이유는 예시 이미지에 라이언과 같이 중복된 좌표가 요소로 들어갈 수 있기 때문이다.
집합이 비었다면 발견된 2 * 2 영역이 없었다는 의미가 되며 집합은 순서를 보장하기 않기에 각 행을 기준으로 먼저 정렬하고 열을 기준으로 정렬하며 집합의 개수 만큼이 지워진 캐릭터들을 의미한다.
remove 메서드를 사용한다면 현재 리스트에서 값이 사라지기에 인덱스 오류를 수정하는것이 복잡하기에 적합하지 않다. 단순히 현재 행렬의 요소가 지워졌다는 뜻으로 "0"으로 치환해주고 "0"과 다른 문자열이 발견되지 않을 때 까지 두 행의 위치를 바꿔주기만 한다면 위에 존재하는 캐릭터를 아래로 내려 오게끔 만들 수 있다.
from collections import deque
def solution(m, n, board):
answer = 0
que = deque([[char for char in item] for item in board])
while True:
d_set = set()
for i in range(m):
for j in range(n):
p = que[i][j]
if p == "0":
continue
if (
i + 1 < m
and j + 1 < n
and que[i][j + 1] == p
and que[i + 1][j] == p
and que[i + 1][j + 1] == p
):
d_set.add((i, j))
d_set.add((i, j + 1))
d_set.add((i + 1, j))
d_set.add((i + 1, j + 1))
if not d_set:
break
for i, j in sorted(d_set, key=lambda x: (x[0], x[1])):
que[i][j] = "0"
answer += 1
while i > 0 and que[i - 1][j] != "0":
que[i][j], que[i - 1][j] = que[i - 1][j], que[i][j]
i -= 1
return answer
