Prison Cells After N Days

8명을 수용할 수 있는 독방이 있다. 누가 들어가있거나(1) 비어있다(0).

하루가 지날 때마다 다음 규칙이 적용된다:

• 어떤 방 양 옆에 두 개의 인접한 방이 있는데 이 두 개가 모두 차있거나 비어있으면, 그 방은 누가 들어온다.
• 아니면 방이 빈다.

참고로 독방은 1차원 배열로 들어오기 때문에 양 끝에 있는 두 방은 양 옆의 인접한 방이 없다.

n 일 후의 독방 상태를 구해보자.

문제 파악

문제가 대체 뭔 말인지 이해하는 데에도 연습이 필요하다는 걸 깨닫게 해준 문제다.

일단 조건에 따라 방의 상태가 바뀌기 때문에 시뮬레이션을 해야 할 것이다. 그런데 문제의 조건을 보면 n이 최대 10^9까지 가능하기 때문에, 최대 이 날짜만큼 그냥 시뮬레이션하게 되면 엄청 느리다.

따라서 우리가 집중해야 하는 것은 방의 개수가 8개 밖에 안된다는 점이다. 거기에 누가 들어있으면 1, 비었으면 0이기 때문에 방 하나가 가질 수 있는 상태는 두 개밖에 안된다. 그러므로 며칠이 지나든 간에, 전체 독방이 가질 수 있는 상태의 개수는 2^8 = 256개 로 많지 않다.

따라서, 시뮬레이션을 하긴 할 건데, 가능한 상태가 256개 밖에 안되므로 무조건 중복된 상태가 나오게 된다. 즉, 일단 최대 256개 만큼의 상태를 다 겪고 나면 그 다음부터는 반복이다. 그러므로 이 반복을 없애는 것이 이 문제 풀이의 핵심이다.

시뮬레이션 + 빨리감기

일단 다음 날짜로 진행하는 시뮬레이션을 구현하면 다음과 같다.

def next_day(cells):
    ret = [0]
    for i in range(1, len(cells) - 1):
        ret.append(1 if cells[i-1] == cells[i+1] else 0)

    ret.append(0)
    return ret

• 양 옆에 방이 있고 두 방의 상태가 같아야만 누가 들어올(1) 수 있다. 즉, 어떤 상태에서 시작하든 간에 다음 날 양 끝에 있는 방 두 개는 항상 비게 된다(ret = [0] 부분과 마지막 ret.append(0)).

그러면 빨리감기 없는 무식한 시뮬레이션을 다음과 같이 구현할 수 있다.

def prisonAfterNDays(cells, n):
    while n > 0:
        n -= 1
        cells = next_day(cells)
    return cells

물론 이대로 해도 작은 입력에 대해서는 잘 동작할 것이다. 하지만 앞서 생각했듯 상태의 개수가 256개 밖에 안되기 때문에, 큰 입력에 대해서는 이전에 했던 계산을 계속 중복할 것이다. 엄청난 비효율이다.

그럼 날짜를 하루 씩 진행하다가, 이전에 이미 겪었던 상태를 또 겪게 되는 순간 빨리감기를 하면 된다.

다음과 같은 상황을 생각해보자.

 day_(n)  ->  day_(n-1)  -> .... ->  day_(n-p)
state_(i) -> state_(i+1) -> .... -> state_(i+p)

상태가 중복된다는 것은 결국 어떤 주기(period)가 있다는 뜻이다. 위에서 우리는 날짜를 n에서 하루씩 빼면서 다음 날을 시뮬레이션 하고 있었다. 따라서 어떤 주기 p에 대해서 위 그림과 같이 날짜와 상태가 진행될 것이다.

따라서, 각 상태마다 날짜를 해시테이블에 기록해두면, 나중에 그 상태가 처음으로 또 발견되는 순간 주기를 알 수 있다. 위 그림으로 설명하면 state_(i)에 대해서 n 값을 저장하고 있다가, 이거랑 중복되는 상태인 state_(i+p)가 처음으로 나오면 이전의 날짜에서 이 날의 날짜를 빼주면 주기를 구할 수 있다. 즉, n - (n - p) = p이다.

주기를 알아 내고 나면 빨리감기는 모듈러 연산으로 쉽게 가능하다. 즉 전체 n 일 만큼을 진행해야 하는데 주기가 p이면 p * (n//p) 만큼의 날짜는 일일이 시뮬레이션 해도 의미없으므로 곧 n % p 만큼만 더 시뮬레이션 하면 된다.

여기서 날짜를 진행할 때 0일부터 시작해서 n일 까지 가는 것보다는 n을 하루 씩 까먹는게 좋다. 왜냐하면 주기를 발견한 순간 남은 날짜를 모듈러 연산으로 줄여버리는 편이 더 쉽기 때문이다. 주기를 반복해서 목표한 n일에 가깝게 날짜를 증가시키는 계산은 생각해내기가 더 어렵다.

아무튼 이 아이디어를 코드로 구현하면 다음과 같다.

def prisonAfterNDays(cells, n):
    states = dict()
    while n > 0:
        key = tuple(cells)  # key must be hashable
        if key not in states:
            states[key] = n  # state_(i) = day_(n)
        else:
            period = states[key] - n  # day_(n) - day_(n-p) = p
            n = n % period

        # if there is still some days, then proceed
        if n > 0:
            n -= 1
            cells = next_day(cells)
    return cells

• 상태를 기록하기 위해서 딕셔너리(해시테이블)을 썼다. 이때 딕셔너리의 키는 해싱 가능해야 하는데 리스트는 해싱할 수 없기 때문에, 독방을 튜플로 바꿔서 키로 사용한다.
• 지금 상태가 이전에 한번도 만난적 없으면 현재 날짜를 기록한다. 위 그림에서 state_(i) = day_(n)에 해당한다.
• 만약 지금 상태를 이전에도 본 적이 있다면 곧바로 주기를 계산할 수 있다. 위 그림에서 state_(i+p) = day_(n-p)에 해당한다. 이전 날짜에서 지금 날짜를 빼주면 주기가 된다.
• 주기를 구하고 나면 남은 주기는 하루씩 진행할 필요 없이 바로 나머지 연산을 때려버릴 수 있다.
• 이러고 나서도 남은 날짜가 있으면 이건 하루씩 진행한다.