[TIL] 20240327 31일차
프로그래머스 프렌즈4블록 문제
https://school.programmers.co.kr/learn/courses/30/lessons/17679
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
해당 문제를 보고 생각한 흐름은 이랬다.
1. 원본 input 값(board)을 사용하면서 진행 (→ 실패. use_board를 정의하고 이를 사용하여 해결)
2. 전체 과정 분석
① 2x2 사이즈 영역 내에 같은 문자가 있는 경우 index값 별도 저장 (리스트 'checked')
② 'checked'에 저장해둔 index 값을 확인하며 2x2 사이즈 영역 내의 같은 문자들 모두 공백으로 변경 및 카운팅
③ 공백들 지우면서 요소들 밀어놓기
3. 2번 과정을 checked에 저장되는 요소 값이 없을 때까지 반복
1.
여기서 2 - ③의 밀어놓는 과정을 진행하려면 원본 input 값(board)을 그대로 사용할 수 없었다.
그래서 board를 시계 방향으로 90도 회전한 use_board를 만들었다.
use_board를 생성하는 코드는 아래와 같다.
use_board = []
for i in range(n):
tmp = []
for j in range(m):
tmp.append(board[m - 1 - j][i])
use_board.append(tmp)
use_board는 board를 회전한 것이므로
board에서 row의 개수에 해당하는 m과 각 row의 길이에 해당하는 n이
use_board에서는 n이 row의 개수, m은 각 row의 길이에 해당하게 된다.
그리고 use_board의 i번째 row는
board의 i번째 column을 역순으로 나열한 것이 된다.
이들을 코드로 구현한 것이다.
2.
use_board를 준비하면
① 2x2 사이즈 영역 내에 같은 문자가 있는 경우 index값 별도 저장 (리스트 'checked')
② 'checked'에 저장해둔 index 값을 확인하며 2x2 사이즈 영역 내의 같은 문자들 모두 공백으로 변경 및 카운팅
③ 공백들 지우면서 요소들 밀어놓기
①, ②, ③을 반복한다. 반복의 탈출 조건은 ① 과정에서 checked에 저장되는 요소가 없어야 한다.
①
2x2 사이즈 영역 내에 동일한 문자가 있는지 확인한다.
확인할 때는 row와 column을 맨 뒤를 제외한 나머지까지만 확인하도록 했다.
즉 위의 예시 그림에서 첫번째 row인 CAAC 에서 ①C, ②A, ③A 까지만 확인한다.
①C를 확인할 때 C의 오른쪽 옆과 아래, 그리고 오른쪽 아래 대각선 방향의 요소를 모두 확인하기 때문이다. (그림의 빨간색 점선 참고)
이를 코드로 구현하면 아래와 같다.
for i in range(n - 1):
for j in range(m - 1):
if use_board[i][j] == use_board[i][j + 1] == use_board[i + 1][j] == use_board[i + 1][j + 1] is not None:
checked.append((i, j))
if 문에서 2x2 사이즈 영역 내의 문자들이 모두 같은지, 그리고 이들이 비어있지 않은지(is not None) 확인한다.
조건을 만족하면 체크한 좌표값을 checked 에 저장한다.
반복 탈출 조건 확인
checked의 요소 개수를 확인한다.
items 변수에 이를 저장하고 만약 요소가 없다면(items == 0) 반복문을 탈출한다.
items = len(checked)
if items == 0:
break
②
checked에 요소가 존재한다면
checked에서 요소를 하나씩 빼면서(pop)
2x2 사이즈 영역 내의 문자들을 공백 문자(' ')로 변경함과 동시에 개수를 카운팅한다.
for _ in range(items):
item = checked.pop()
i = item[0]
j = item[1]
if use_board[i][j] != ' ':
use_board[i][j] = ' '
answer += 1
if use_board[i][j + 1] != ' ':
use_board[i][j + 1] = ' '
answer += 1
if use_board[i + 1][j] != ' ':
use_board[i + 1][j] = ' '
answer += 1
if use_board[i + 1][j + 1] != ' ':
use_board[i + 1][j + 1] = ' '
answer += 1
③
공백 문자들을 제거하면서 요소들을 앞으로 미는 작업이 필요하다.
그러면서도 전체 틀에 변형이 있으면 안되므로 비어있게 되는 부분은 None으로 해준다.
이 과정을 구현하기 위해 while문과 del 함수를 이용했다.
for i in range(n):
for j in range(m):
if use_board[i][j] == ' ':
while use_board[i][j] == ' ':
del use_board[i][j]
use_board[i].append(None)
use_board의 모든 요소(위치)를 확인하면서
만약 그 위치에 공백 문자가 있다면 그 위치에 공백 문자가 확인되지 않을 때까지
해당 위치의 요소를 지우고(del)
그 row의 맨 뒤에 None을 삽입(append)한다.
이 과정을 진행하고 나면 공백 문자들을 제거하면서
요소들을 앞으로 밀면서 동시에 비어있는 칸은 None으로 변경되는 결과를 볼 수 있다.
이렇게 ①, ②, ③ 과정을 checked에 요소가 추가되지 않을 때까지(반복 탈출 조건 만족 시까지)
while문을 통해 반복한다.
while문을 탈출하면 ② 과정에서 카운팅한 개수를 리턴하고 종료한다.
아래는 전체 코드이다.
def solution(m, n, board):
# 전체 과정
# 1. 2x2 사이즈 영역 내에 같은 문자가 있는 경우 index값 별도 저장 (리스트 'checked')
# 2. 'checked'에 저장해둔 index 값을 확인하며 2x2 사이즈 영역 내의 같은 문자들 모두 공백으로 변경 및 카운팅
# 3. 공백들 지우면서 요소들 밀어놓기
# 1 ~ 3을 checked에 요소가 추가되지 않을 때까지 반복
checked = [] # 2x2 사이즈 영역 같은 문자 확인 시 좌표 값 저장해두는 리스트
use_board = [] # 1 ~ 3 과정 진행을 위해 board를 시계 방향으로 90도 회전하여 저장하는 2차원 리스트
answer = 0 # 리턴값
# 전체 과정을 진행하기 위해 use_board 정의
# use_board는 board를 시계 방향으로 90도 회전한 것
for i in range(n):
tmp = []
for j in range(m):
tmp.append(board[m - 1 - j][i])
use_board.append(tmp)
# 1 ~ 3 반복
while True:
# 1. 2x2 사이즈 영역 내에 같은 문자가 있는 경우 index값 별도 저장 (리스트 'checked')
for i in range(n - 1):
for j in range(m - 1):
if use_board[i][j] == use_board[i][j + 1] == use_board[i + 1][j] == use_board[i + 1][j + 1] is not None:
checked.append((i, j))
# checked의 요소 개수
items = len(checked)
# 반복 중단 조건 체크. 2x2 사이즈 영역 같은 문자 없을 시 종료
if items == 0:
break
# 2. 'checked'에 저장해둔 index 값을 확인하며 2x2 사이즈 영역 내의 같은 문자들 모두 공백으로 변경 및 카운팅
for _ in range(items):
item = checked.pop()
i = item[0]
j = item[1]
if use_board[i][j] != ' ':
use_board[i][j] = ' '
answer += 1
if use_board[i][j + 1] != ' ':
use_board[i][j + 1] = ' '
answer += 1
if use_board[i + 1][j] != ' ':
use_board[i + 1][j] = ' '
answer += 1
if use_board[i + 1][j + 1] != ' ':
use_board[i + 1][j + 1] = ' '
answer += 1
# 3. 공백들 지우면서 요소들 밀어놓기
for i in range(n):
for j in range(m):
if use_board[i][j] == ' ':
while use_board[i][j] == ' ':
del use_board[i][j]
use_board[i].append(None)
return answer