💯 Daily LeetCode Challenge Day_03 - Prison Cells After N Days

Explore - LeetCode

---

문제

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.)

Example 1:

Input: cells = [0,1,0,1,1,0,0,1], N = 7 Output: [0,0,1,1,0,0,0,0] Explanation: The following table summarizes the state of the prison on each day: 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]

Example 2:

Input: cells = [1,0,0,1,0,0,1,0], N = 1000000000 Output: [0,0,1,1,1,1,1,0]

Note:

1. cells.length == 8
2. cells[i] is in {0, 1}
3. 1 <= N <= 10^9

---

시키는 데로 구현했다.

N 이 1000000000 으로 억이 넘어가는 범위이다.

일반적으로 1억번 실행이 1초정도 걸린다고 생각하고

대부분 코딩문제는 1초 안에 실행되어야 Time Limit 이 안걸린다고 알고리즘 잘하시는 형에게 들었다.

N번 for 문 돌리니 Time Limit 이 걸린다.

이놈을 어떻게 시간을 줄여야 할까 겁나 생각해도 반복문 하나인데 뭘 더 어떻게 줄일까 싶었다.

어쨋건 시간을 줄일려면 N번 전부 반복문을 돌지 말라는 얘기인것 같아 N번을 다 돌지 않고도

결과값을 찾을 수 있을 지 생각했다.

수학적으로 수식이 있는지 생각해보았고 어떤 패턴이 있는지도 확인해 보았다.

패턴이 있었다.

14번 단위로 같은 패턴이 반복되고 있었다.

그럼 14번까지만 반복문을 돌고 결과는 14를 나눈 나머지 값을 사용하면 끗 👍

class Solution {
    var arr : [Int] = []
    func prisonAfterNDays(_ cells: [Int], _ N: Int) -> [Int] {
        arr = cells
        var answer : [[Int]] = []
        // print(arr)
        for i in 0..<N{
             if (i > 14){
                break
            }
            answer.append(check())
        }
        // print(answer)
        // for i in answer{
        //     print(i)
        // }
        // print(answer[0])
        if N%14 != 0 {
            return answer[N%14 - 1]
        }else{
            return answer[13]
        }
    }
    func check() -> [Int] {
      
        var tmp : [Int] = arr
        tmp[0] = 0
        tmp[7] = 0
         
        for i in 1...6 {
            if arr[i-1] == 0 && arr[i+1] == 0 {
                tmp[i] = 1
            }else if arr[i-1] == 1 && arr[i+1] == 1 {
              tmp[i] = 1
                
            }else{
                tmp[i] = 0
            }
        }
        arr = tmp
        // print(arr)
        return arr
    }
    
}