문제 개요
한 줄로 늘어선 8개의 감옥 칸이 있으며, 각 칸에는 수감자가 있거나 비어 있습니다. 매일이 지나면 각 칸의 점유 여부가 다음 규칙에 따라 바뀝니다.
어떤 칸의 양쪽 이웃 칸이 모두 점유 중이거나 모두 비어 있는 경우, 해당 칸은 다음 날 점유 상태가 됩니다.
그 외의 경우에는 해당 칸이 비게 됩니다.
참고로 맨 왼쪽 칸과 맨 오른쪽 칸은 이웃이 하나뿐이기 때문에, 하루가 지나면 항상 빈 칸으로 바뀝니다.
감옥의 현재 상태는 배열 cells로 표현합니다. i번째 칸에 수감자가 있으면 cells[i] = 1, 비어 있으면 cells[i] = 0입니다.
따라서 초기 상태가 주어졌을 때 N일 후의 감옥 상태를 반환하는 것이 이 문제의 목표입니다.
예시
입력이 [0,1,0,1,1,0,0,1]이고 N = 7이라면 출력은 [0,0,1,1,0,0,0,0]이 됩니다. 7일 동안 상태가 변화하는 과정은 다음과 같습니다.
Day 0: [0, 1, 0, 1, 1, 0, 0, 1] Day 1: [0, 1, 1, 0, 0, 0, 0, 0] Day 2: [0, 0, 0, 0, 1, 1, 1, 0] Day 3: [0, 1, 1, 0, 0, 1, 0, 0] Day 4: [0, 0, 0, 0, 0, 1, 0, 0] Day 5: [0, 1, 1, 1, 0, 1, 0, 0] Day 6: [0, 0, 1, 0, 1, 1, 0, 0] Day 7: [0, 0, 1, 1, 0, 0, 0, 0]
접근 방법: 주기성 활용하기
N이 매우 클 때 매일 하나씩 시뮬레이션하면 비효율적입니다. 다행히 이 문제에는 중요한 성질이 숨어 있습니다. 하루가 지나면 양 끝 칸이 항상 0으로 고정되므로 실제로 변할 수 있는 칸은 가운데 6개뿐이고, 그 결과 감옥의 상태는 14일을 주기로 반복됩니다.
따라서 처음 14일까지만 시뮬레이션해 두고, N을 14로 나눈 나머지에 해당하는 날짜의 상태를 찾으면 됩니다. 이렇게 하면 N이 아무리 커도 일정한 시간 안에 답을 구할 수 있습니다.
알고리즘 단계
map 타입의 m과 set 타입의 visited를 준비합니다.
N이 0이면 cells를 그대로 반환합니다.
현재 cells 상태를 visited 집합에 삽입합니다.
i를 1부터 14까지 반복하면서 다음을 수행합니다.
크기가 8인 배열 temp를 생성합니다.
j를 1부터 6까지 반복하면서, cells[j − 1] XOR cells[j + 1]의 값이 0이면 temp[j]를 1로 설정합니다.
cells를 temp로 갱신하고, m[i]에 temp를 저장한 뒤 temp를 visited에 삽입합니다.
N이 14로 나누어 떨어지면 m[14]를, 그렇지 않으면 m[N mod 14]를 반환합니다.
다음 구현 예제를 통해 좀 더 자세히 이해해 보겠습니다.
C++ 구현 예제
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<int> v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << v[i] << ", ";
}
cout << "]"<<endl;
}
class Solution {
public:
vector<int> prisonAfterNDays(vector<int>& cells, int N) {
map <int, vector <int> > m;
if(N == 0) return cells;
set <vector <int> > visited;
visited.insert(cells);
for(int i = 1; i<=14 ; i++ ){
vector <int> temp(8);
for(int j = 1; j < 7; j++){
if(cells[j - 1] ^ cells[j + 1] == 0){
temp[j] = 1;
}
}
cells = temp;
m[i] = temp;
visited.insert(temp);
}
return m[N % 14 == 0? 14 : N % 14];
}
};
main(){
vector<int> v1 = {0,1,0,1,1,0,0,1};
Solution ob;
print_vector(ob.prisonAfterNDays(v1, 7));
}
입력
[0,1,0,1,1,0,0,1] 7
출력
[0,0,1,1,0,0,0,0]