백준 15787 - 기차가 어둠을 헤치고(파이썬)

https://www.acmicpc.net/problem/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번째 줄까지 각 줄에 명령이 주어진다. 

출력

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

예제 입력 1

5 5
1 1 1
1 1 2
1 2 2
1 2 3
3 1

예제 출력 1

2

---

정답 코드 - 2차원 리스트를 이용한 풀이

n, m = map(int, input().split())
train = [[0] * 20 for _ in range(n)]
cnt = 0
# 명렁어 처리
# n=100000
for _ in range(m):
    cmd = list(map(int, input().split()))
    # print(cmd)
    # i번째 기차에(1 ≤ i ≤ N) x번째 좌석에(1 ≤ x ≤ 20) 사람을 태워라.
    # 이미 사람이 타있다면 , 아무런 행동을 하지 않는다.
    # cmd[0]:명령 번호, cmd[1]:기차 번호, cmd[2]좌석 번호
    if cmd[0] == 1:
        train[cmd[1]-1][cmd[2]-1] = 1

    # i번째 기차에(1 ≤ i ≤ N) x번째 좌석에(1 ≤ x ≤ 20) 사람을 하차시킴.
    # 이미 빈자리? 아무런 행동을 하지 않는다.
    elif cmd[0] == 2:
        train[cmd[1]-1][cmd[2]-1] = 0

    # i번째 기차의 좌석, 한칸 씩 뒤로 이동 pop->insert
    # n=20
    elif cmd[0] == 3:
        train[cmd[1]-1].pop()
        train[cmd[1]-1].insert(0, 0)

    # i번째 기차의 좌석, 한칸 씩 앞으로 이동
    # n=20
    else:
        train[cmd[1]-1].pop(0)
        train[cmd[1]-1].append(0)

# for t in train:
#     print(t)

memory = []
# 기차 출발
for i in range(n):
    # print(f'{i}번째 기차: {train[i]}')
    # 기차 t가 memory에 있으면
    if train[i] not in memory:
        cnt += 1
        memory.append(train[i])

# print(memory)
print(cnt)

메모리: 53124kb 시간:396ms

엣지 케이스

처음엔 train을 n+1개 좌석 수를 21개로 설정해서 1부터 인덱싱 해서 바로 결과를 냈지만

네번째 명령을 수행할 때 논리에 오류가 발생하게 되었다. 네번째 명령은 탑승 중인 모든 승객을 앞으로 한칸씩 이동하는 것인데, 0번부터 20번까지 21개 좌석을 만들어 놓았기 때문에 1번에 있는 승객이 0번 좌석으로 이동하는 일이 발생했다. 그래도 정답은 좌석수를 기준으로 하는 게 아닌 은하수를 건넌 기차의 수를 기준으로 하기 때문에 조치를 취하지 않아도 괜찮을 거라 생각했지만 반례가 있었던 것이다.

만약 배치 상태가 10000...0인 것과 00000...0인 기차가 있다고 할 때 4번 명령을 수행한 뒤 상태는 두 기차 모두 00000...0이 되어야한다.

하지만 내 코드의 경우 0번 좌석도 존재하기 때문에 별다른 조치를 취하지 않으면 전자는 10000...0 후자는 00000...0이 되기 때문에 서로 다른 결과가 나오게 된다.

따라서 좌석의 수를 원래대로 다루는 게 맞는 것이다.

 

정답 코드 - 비트마스킹을 이용한 풀이

n, m = map(int, input().split())
train = [0] * n
cnt = 0
# 명령어 처리
# n=100000
for _ in range(m):
    cmd = list(map(int, input().split()))
    # print(cmd)
    # i번째 기차에(1 ≤ i ≤ N) x번째 좌석에(1 ≤ x ≤ 20) 사람을 태워라.
    # 이미 사람이 타있다면 , 아무런 행동을 하지 않는다.
    # cmd[0]:명령 번호, cmd[1]:기차 번호, cmd[2]좌석 번호
    if cmd[0] == 1:
        e = 20 - cmd[2]
        train[cmd[1] - 1] |= (1 << e)

    # i번째 기차에(1 ≤ i ≤ N) x번째 좌석에(1 ≤ x ≤ 20) 사람을 하차시킴.
    # 이미 빈자리? 아무런 행동을 하지 않는다.
    elif cmd[0] == 2:
        e = 20 - cmd[2]
        train[cmd[1] - 1] &= ~(1 << e)

    # i번째 기차의 좌석, 한칸 씩 뒤로 이동 pop->insert
    # n=20
    elif cmd[0] == 3:
        train[cmd[1] - 1] >>= 1

    # i번째 기차의 좌석, 한칸 씩 앞으로 이동
    # n=20
    else:
        train[cmd[1] - 1] <<= 1
        #앞으로 보낸 사람이 0번째 좌석이면 하차시키는 코드
        train[cmd[1] - 1] &= ~(1 << 20)

memory = []
# 기차 출발
for i in range(n):
    if train[i] not in memory:
        cnt += 1
        memory.append(train[i])

print(cnt)

메모리: 31616kb 시간:4236ms

 

비트마스크 개념 참고 - https://brotherstone.tistory.com/75

Python 비트 마스크(Bit Mask)

 

피드백

처음엔 평소처럼 2차원 리스트를 이용해 구현했고 두번째 풀이는 비트마스크 개념을 공부한 뒤에 그 방법으로 풀어봤다.

어차피 입력받은 명령대로 좌석표시를 true, false로 표현해주면 되기 때문에 bool이나 int형보다 비트를 사용하는게 자원을 덜 쓰기 때문에 시도하게 되었다.

결과적으로 메모리는 후자가 훨씬 덜 사용했지만 시간은 오히려 소폭 늘어났다.