[Python/BOJ] 15787. 기차가 어둠을 헤치고 은하수를

https://www.acmicpc.net/problem/15787

15787번: 기차가 어둠을 헤치고 은하수를

문제

N개의 기차가 어둠을 헤치고 은하수를 건너려고 한다.

기차는 20개의 일렬로 된 좌석이 있고, 한 개의 좌석에는 한 명의 사람이 탈 수 있다. 

기차의 번호를 1번부터 N번으로 매길 때, 어떠한 기차에 대하여 M개의 명령이 주어진다.

명령의 종류는 4가지로 다음과 같다.

• 1 i x : i번째 기차에(1 ≤ i ≤ N) x번째 좌석에(1 ≤ x ≤ 20) 사람을 태워라. 이미 사람이 타있다면 , 아무런 행동을 하지 않는다.
• 2 i x : i번째 기차에 x번째 좌석에 앉은 사람은 하차한다. 만약 아무도 그자리에 앉아있지 않았다면, 아무런 행동을 하지 않는다.
• 3 i : i번째 기차에 앉아있는 승객들이 모두 한칸씩 뒤로간다. k번째 앉은 사람은 k+1번째로 이동하여 앉는다. 만약 20번째 자리에 사람이 앉아있었다면 그 사람은 이 명령 후에 하차한다.
• 4 i : i번째 기차에 앉아있는 승객들이 모두 한칸씩 앞으로간다. k번째 앉은 사람은 k-1 번째 자리로 이동하여 앉는다. 만약 1번째 자리에 사람이 앉아있었다면 그 사람은 이 명령 후에 하차한다.

M번의 명령 후에 1번째 기차부터 순서대로 한 기차씩 은하수를 건너는데 조건이 있다.

기차는 순서대로 지나가며 기차가 지나갈 때 승객이 앉은 상태를 목록에 기록하며 이미 목록에 존재하는 기록이라면 해당 기차는 은하수를 건널 수 없다.

예를 들면, 다음 그림을 예로 들었을 때, 1번째 기차와 같이 승객이 앉은 상태는 기록되지 않았기 때문에 은하수를 건널 수있다. 2번째 기차와 같은 상태도 기록되지 않았기 때문에 2번째 기차도 은하수를 건널 수 있다. 3번째 기차는 1번째 기차와 승객이 앉은 상태가 같으므로 은하수를 건널 수 없다.

처음에 주어지는 기차에는 아무도 사람이 타지 않는다.

은하수를 건널 수 있는 기차의 수를 출력하시오.

입력

입력의 첫째 줄에 기차의 수 N(1 ≤ N ≤ 100000)과 명령의 수 M(1 ≤ M ≤ 100000)가 주어진다. 이후 두 번째 줄부터 M+1번째 줄까지 각 줄에 명령이 주어진다. 

출력

은하수를 건널 수 있는 기차의 수를 출력하시오.

풀이

Code

import sys
input = sys.stdin.readline


def solution() :
    # 1. 사람 태우기 함수 정의
    def command_1(i, x) :
        # 1-1. 해당 기차에 x가 없을 경우 삽입
        if x not in array[i] : array[i].append(x)
    # 2. 하차 함수 정의
    def command_2(i, x) :
        # 2-1. 해당 기차에 x가 있을 경우 제거
        try : array[i].pop(array[i].index(x))
        except : return
    # 3. 승객을 뒤로 1칸 미루기 함수 정의
    def command_3(i) :
        out = -1
        # 3-1.
        for x in range(len(array[i])) :
            # 미루기
            array[i][x] += 1
            # 하차해야 하는 경우 승객 체크
            if array[i][x] == 21 : out = x
        # 3-2. 하차해야 하는 경우
        if out != -1 :
            array[i].pop(out)
    # 4. 승객을 앞으로 1칸 당기기 함수 정의
    def command_4(i) :
        out = -1
        # 4-1.
        for x in range(len(array[i])) :
            # 당기기
            array[i][x] -= 1
            # 하차해야 하는 경우 승객 체크
            if array[i][x] == 0 : out = x
        # 4-2. 하차해야 하는 경우
        if out != -1 :
            array[i].pop(out)

    n, m = map(int, input().split())
    # 5. 기차 리스트 생성
    array = [[] for _ in range(n+1)]
    # 6.
    for _ in range(m) :
        # 6-1. 명령 입력받기
        command = list(map(int, input().split()))
        # 6-2. 명령 수행하기
        if command[0] == 1 : command_1(command[1], command[2])
        elif command[0] == 2 : command_2(command[1], command[2])
        elif command[0] == 3 : command_3(command[1])
        elif command[0] == 4 : command_4(command[1])
    # 7. 중복 제거
    ans_lst = []
    for lst in array[1:] :
        if sorted(lst) not in ans_lst : ans_lst.append(sorted(lst))
    # 8. 결과 출력
    print(len(ans_lst))

if __name__ == "__main__":
    solution()