1과 0으로만 이루어진 리스트와 정수 k가 주어졌다고 가정해 봅시다. 리스트의 각 값은 감옥의 한 칸(cell) 상태를 나타내며, 1은 점유된 칸, 0은 비어 있는 칸을 의미합니다.
매일 모든 칸은 다음 규칙에 따라 상태가 바뀝니다. 어떤 칸의 양옆에 인접한 두 칸이 서로 같은 상태(둘 다 점유 또는 둘 다 비어 있음)라면 해당 칸은 점유 상태(1)가 되고, 그렇지 않으면 빈 칸(0)이 됩니다. 우리가 구해야 하는 것은 k일이 지난 후 감옥 칸들의 최종 상태입니다.
예를 들어 nums = [1, 0, 1, 0, 0, 0, 0, 0], k = 1이 입력으로 주어지면 출력은 [0, 1, 1, 0, 1, 1, 1, 0]입니다. 첫 번째 칸과 마지막 칸은 이웃이 두 개 존재할 수 없기 때문에 어떤 경우에도 점유 상태가 될 수 없습니다.
문제 해결 접근 방법
이 문제는 다음 단계를 따라 해결할 수 있습니다.
- next_day_state() 함수 정의: 현재 cells 상태를 받아 하루가 지난 후의 상태를 반환합니다.
- new_cells := cells의 복사본 생성
- new_cells[0] := 0, new_cells[7] := 0 (첫 칸과 마지막 칸은 항상 빈 칸)
- j를 1부터 6까지 반복하면서:
- cells[j - 1]과 cells[j + 1]이 같으면 new_cells[j] := 1
- 그렇지 않으면 new_cells[j] := 0
- new_cells 반환
- 메인 메서드(solve)에서 수행할 작업:
- seen := 새로운 딕셔너리(맵)
- flag := False, i := 0으로 초기화
- i < N인 동안 반복:
- ns := next_day_state(cells)
- ns가 seen에 없다면 seen에 기록
- 이미 존재한다면 flag := True로 설정하고 루프 탈출(순환 발견)
- cells := ns, i := i + 1
- flag가 True라면(상태가 순환하는 경우):
- N := N mod (seen에 기록된 상태의 개수)
- i := 0으로 초기화한 뒤 i < N인 동안 next_day_state()를 반복 호출하여 남은 일수만큼 상태를 갱신
- 최종 cells 반환
핵심 아이디어: 상태 순환 감지
k가 매우 큰 값일 수 있으므로 매일 상태를 하나씩 계산하면 비효율적입니다. 다행히 감옥 상태의 조합은 유한하기 때문에(칸이 8개이므로 최대 256가지) 반드시 순환이 발생합니다. 이미 등장했던 상태가 다시 나타나는 시점을 감지하면, N을 순환 길이로 나눈 나머지만큼만 추가로 계산하면 됩니다. 덕분에 k가 아무리 커도 빠르게 정답을 구할 수 있습니다.
구현 예제
import copy
class Solution:
def next_day_state(self, cells):
new_cells = copy.copy(cells)
new_cells[0] = 0
new_cells[7] = 0
for j in range(1, 7):
if cells[j - 1] == cells[j + 1]:
new_cells[j] = 1
else:
new_cells[j] = 0
return new_cells
def solve(self, cells, N):
seen = dict()
flag, i = False, 0
while i < N:
ns = self.next_day_state(cells)
if tuple(ns) not in seen:
seen[tuple(ns)] = True
else:
flag = True
break
cells = ns
i += 1
if flag:
N = N % len(seen)
i = 0
while i < N:
ns = self.next_day_state(cells)
i += 1
cells = ns
return cells
ob = Solution()
nums = [1, 0, 1, 0, 0, 0, 0, 0]
k = 1
print(ob.solve(nums, k))입력
[1, 0, 1, 0, 0, 0, 0, 0], 1
출력
[0, 1, 1, 0, 1, 1, 1, 0]