Day3

Prison Cells After N Days

문제

There are 8 prison cells in a row, and each cell is either occupied or vacant.

Each day, whether the cell is occupied or vacant changes according to the following rules:

• If a cell has two adjacent neighbors that are both occupied or both vacant, then the cell becomes occupied.
• Otherwise, it becomes vacant.

(Note that because the prison is a row, the first and the last cells in the row can't have two adjacent neighbors.)

We describe the current state of the prison in the following way: cells[i] == 1 if the i-th cell is occupied, else cells[i] == 0.

Given the initial state of the prison, return the state of the prison after N days (and N such changes described above.)

답(Java)

class Solution {
    public int[] prisonAfterNDays(int[] cells, int N) {
    	int M = N > 14 ? N % 14 + 14 : N;
    	
        for (int i = 0; i < M; ++i) {
            int prevCell = 0;
            for (int j = 0; j < 8; ++j) {
                if (j == 0 || j == 7) {
                    prevCell = cells[j];
                    cells[j] = 0;
                    continue;                    
                }
                if (prevCell == cells[j+1]) {
                    prevCell = cells[j];
                    cells[j] = 1;
                    continue;
                }
                prevCell = cells[j];
                cells[j] = 0;
        	}
        }
        return cells;
    }
}

양 끝의 방은 Day0에만 occupied고 그 이후에는 조건에 따라 반드시 vacant이다. 나머지 6개 방은 0 또는 1의 값을 가질 수 있다. 단순히 생각했을 때 아무리 길어도 2^6 = 64개의 조합이 반복될 것이다. 실제로 몇 개의 조합이 반복되는지 확인한 결과, 14개의 조합이 반복되는 것을 확인했다. 14개의 조합이 반복되므로 M = N % 14를 계산하여 M만큼만 패턴을 계산하도록 구현했다. Day0에서 양 끝 방이 occupied인 경우는 반복 패턴에서 제외되므로 14를 더해 반복 패턴을 맞춰주었다.