이 글은 Velog에서 이전한 글입니다. Velog 원문 보기
1번 문제: BFS
문제: https://leetcode.com/problems/minesweeper/description/
풀이 소요 시간: 30분
알고리즘: BFS
from collections import deque
d = [[-1,-1], [-1,0], [0,-1], [1,1], [1,0], [0,1], [1,-1], [-1,1]]
class Solution:
def updateBoard(self, board: List[List[str]], click: List[int]) -> List[List[str]]:
R, C = len(board), len(board[0])
q = deque([(click[0], click[1])])
if board[click[0]][click[1]] == 'M':
board[click[0]][click[1]] = 'X'
return board
while q:
x, y = q.popleft()
if board[x][y] != 'E':
continue
cnt = 0
for dx, dy in d:
nx, ny = x+dx, y+dy
if 0<=nx<R and 0<=ny<C:
if board[nx][ny] == 'M':
cnt += 1
if cnt > 0: # 주변에 폭탄이 1개 이상 있는 경우
board[x][y] = str(cnt)
else: # 주변에 지뢰가 없는 경우 (재귀적으로 주변 확장)
board[x][y] = 'B'
for dx, dy in d:
nx, ny = x+dx, y+dy
if 0<=nx<R and 0<=ny<C:
if board[nx][ny] == 'E':
q.append((nx, ny))
return board풀이 사고 흐름
- 우선 크게 2가지 경우로 분류해서 생각
- 주변에 폭탄이 1개 이상 있는 경우
- 주변에 지뢰가 없는 경우
- 현재 칸 주변 8방향 지뢰 개수를 체크
- 지뢰 개수(cnt) > 0 이면 현재 칸을 cnt로 변경하고 끝
- cnt == 0이면 현재 칸을 'B'로 바꾸고, 주변 'E'만 큐에 삽입
if board[x][y] != 'E':
이미 처리된 값은 continue로 스킵
멘토님 피드백
M,B같은 문제에서 의미를 가지는 값은 별도 상수로 관리하는 것을 추천- 상수로 관리해야 재사용 할 때 실수를 안한다.
x+dx같은 부분 띄어쓰기 추가해서x + dx로 표기 -> 사소해보이지만 가독성에 큰 차이를 줌cnt같은 변수명boom_cnt로 의미가 명확하게 변경x, y = q.popleft(): 큐에 들어가는 값에 대한 설명 주석을 작성해야 한다.- 시간복잡도 생각해보기 (worst case까지)
2번 문제: DP
문제: https://leetcode.com/problems/remove-boxes/description/
풀이 소요 시간: x
알고리즘: DP
처음에는 문제 이해가 어려웠다.
문제는 여러 개의 박스가 주어지며, 각 박스는 서로 다은 양의 정수로 구분한다.
같은 양의 정수로 이루어진 연속된 박스들을 선택할 수 있고,
선택한 박스의 개수를 k라고 할 때 이 박스들을 제거하면 k * k (k**2) points를 얻는다.
문제의 예시로 이해를 해보면
Input: boxes = [1,3,2,2,2,3,4,3,1]
Output: 23
Explanation:
[1, 3, 2, 2, 2, 3, 4, 3, 1]
----> [1, 3, 3, 4, 3, 1] (3*3=9 points)
----> [1, 3, 3, 3, 1] (1*1=1 points)
----> [1, 1] (3*3=9 points)
----> [] (2*2=4 points)1단계
[1, 3, 2, 2, 2, 3, 4, 3, 1]
-> (2,2,2) 제거: k=3
[1, 3, 3, 4, 3, 1]points = 3**2 = 9
가운데 2들의 묶음을 제거해서 3들이 가까워짐
2단계
여기서 가운데에 있는 3의 묶음이 아닌 4를 지워야 한다.
4를 제거하면 3의 묶음이 3개가 되어 k=3이 된다.
[1, 3, 3, 4, 3, 1]
-> (4) 제거: k=1
[1, 3, 3, 3, 1]points = 1**2 = 1
3단계
[1, 3, 3, 3, 1]
-> (3,3,3) 제거: k=3
[1, 1]points = 3**2 = 9
4단계
[1, 1]
(1,1) 제거: k=2
[]points = 2**2 = 4
Result = 9+1+9+4 = 23
논리적으로는 이해했으나, 코드로 구현하는 것에 실패.