백준 15787번 기차가 어둠을 헤치고 은하수를 문제 풀이(Python, 구현, Silver2)

백준 15787번 기차가 어둠을 헤치고 은하수를 문제 바로가기

문제 접근

이 문제에서 3번과 4번 명령을 보고 비트를 떠올렸다.
비트연산에서 shift연산과 매우 유사했다.
따라서 비트로 변환하여 문제를 풀어야겠다고 생각했고, 비트로 명령들을 모두 수행한 후에는 set연산을 통해서 리스트의 중복을 제거해서 총 몇개의 기차가 지날지를 계산해주고자 했다.

문제 풀이

1번 명령

&연산자를 통해 승객이 탑승했는지 안했는지를 확인하고 탑승하지 않았다면 + num을 통해 탑승했음을 표현한다.

if line[0] == 1:
    num = 2**(line[2]-1)
    if train[line[1]] & num != num:
        train[line[1]] += num

2번 명령

&연산자를 통해 승객이 탑승해 있는지 아닌지를 확인해 탑승해있다면 하차시키고 탑승해있지 않다면 아무 연산도 하지 않는다.

 elif line[0] == 2:
        num = 2**(line[2]-1)
        if train[line[1]] & num == num:
            train[line[1]] -= num

3번 명령

20번째에 처리를 안하고 시프트 연산을 하면 전체 비트가 20이 넘어버리는 일이 발생하기 때문에 20번째에서 시프트 연산을 하면 0으로 바꿔주어야 한다.

elif line[0] == 3:
        if train[line[1]] & 2**19 == 2**19:
            train[line[1]] -= 2**19
        train[line[1]] = train[line[1]] << 1

4번 명령

4번 명령 역시 3번 명령과 마찬가지로 0에서 승객이 하차하는 것을 구현해주어야 한다.

elif line[0] == 4:
        if train[line[1]] & 2**0 == 2**0:
            train[line[1]] -= 2**0
        train[line[1]] = train[line[1]] >> 1

결과 개수 구하기

간단하게 set자료형을 통해서 중복을 제거해주면 된다.

result = set(train)

print(len(result))

제출 코드

import sys

N, M = map(int, sys.stdin.readline().split())
train = [0 for i in range(N)]

for i in range(M):
    line = list(map(int, sys.stdin.readline().split()))
    line[1] = line[1]-1
    if line[0] == 1:
        num = 2**(line[2]-1)
        if train[line[1]] & num != num:
            train[line[1]] += num
    elif line[0] == 2:
        num = 2**(line[2]-1)
        if train[line[1]] & num == num:
            train[line[1]] -= num
    elif line[0] == 3:
        if train[line[1]] & 2**19 == 2**19:
            train[line[1]] -= 2**19
        train[line[1]] = train[line[1]] << 1
        
    elif line[0] == 4:
        if train[line[1]] & 2**0 == 2**0:
            train[line[1]] -= 2**0
        train[line[1]] = train[line[1]] >> 1

result = set(train)

print(len(result))