BOJ 15787번(기차가 어둠을 헤치고 은하수를)

난이도

---

실버 II

 

 

 

풀이

---

이차원 배열을 주어진 조건에 맞게 구현하면 되는 문제였다.

 

 

풀이1

풀이1은 리스트를 가지고 구현한 풀이이다.

import sys

input=sys.stdin.readline

N,M=map(int,input().split())

train=[[0 for _ in range(20)]for _ in range(N)]
result=0
answer=[]

for _ in range(M):
    command=list(map(int,input().split()))
    trainIdx=command[1]
    if len(command)==3:
        chain=command[2]
    if command[0]==1:
        train[trainIdx-1][chain-1]=1
    elif command[0]==2:
        train[trainIdx-1][chain-1]=0
    elif command[0]==3:
        if train[trainIdx-1][19]==1:
            train[trainIdx-1][19]=0
        for i in range(18,-1,-1):
            train[trainIdx-1][i+1]=train[trainIdx-1][i]
        train[trainIdx - 1][0]=0
    elif command[0]==4:
        if train[trainIdx-1][0]==1:
            train[trainIdx-1][0]=0
        for i in range(1,20):
            train[trainIdx-1][i-1]=train[trainIdx-1][i]
        train[trainIdx - 1][19] = 0

for tra in train:
    if tra in answer:
        pass
    else:
        answer.append(tra)
        result+=1

print(result)

리스트를 이용한 다른 풀이도 있는데 이게 훨씬 더 간단하긴 하다.

import sys

input=sys.stdin.readline

N,M=map(int,input().split())

train=[[0 for _ in range(20)]for _ in range(N)]
result=0
answer=[]

for _ in range(M):
    command=list(map(int,input().split()))
    trainIdx=command[1]
    if len(command)==3:
        chain=command[2]
    if command[0]==1:
        train[trainIdx-1][chain-1]=1
    elif command[0]==2:
        train[trainIdx-1][chain-1]=0
    elif command[0]==3:
        train[trainIdx-1].insert(0,0)
        train[trainIdx-1].pop(-1)
    elif command[0]==4:
        train[trainIdx-1].pop(0)
        train[trainIdx-1].append(0)

for tra in train:
    if tra in answer:
        pass
    else:
        answer.append(tra)
        result+=1

print(result)

 

 

 

풀이2

풀이2는 리스트말고 deque를 이용해서 구현하였다.

이를 이용하니 풀이1에 비해서는 훨씬 더 코드가 간단해졌다.

import sys
from collections import deque

input=sys.stdin.readline

N,M=map(int,input().split())
answer=[]
result=0
train=[deque(0 for _ in range(20))for _ in range(N)]

for _ in range(M):
    command=list(map(int,input().split()))
    trainIdx=command[1]
    if len(command)==3:
        chain=command[2]

    if command[0]==1:
        train[trainIdx-1][chain-1]=1
    elif command[0]==2:
        train[trainIdx-1][chain-1]=0
    elif command[0]==3:
        train[trainIdx-1].rotate(1)
        train[trainIdx-1][0]=0
    elif command[0]==4:
        train[trainIdx-1].rotate(-1)
        train[trainIdx - 1][19] = 0

for tra in train:
    if tra in answer:
        pass
    else:
        result+=1
        answer.append(tra)


print(result)

 

• 파이썬 deque 문법 정리
  
  파이썬의 리스트와 같이 요소들을 한 곳에 담아두는 배열
  deque는 큐이지만 양방향인 queue이다 : 양 쪽 방향 모두에서 앞뒤 요소를 추가/제거할 수 있다.
  
  1. 큐.append(item)
  2. 큐.appendleft(item)
  3. 큐.pop()
  4. 큐.popleft()
  5. 큐.extend(array)
  6. 큐.extendleft(array)
  7. 큐.remove(item)
  8. 큐.rotate(숫자) : 해당 숫자만큼 회전 - 양수: 시계방향 / 음수 : 반시계방향
  
  

풀이3

비트마스킹을 이용한 풀이

import sys

input=sys.stdin.readline

N,M=map(int,input().split())

trains=[0 for _ in range(N)]
answer=[]
result=0

for _ in range(M):
    commmand=list(map(int,input().split()))
    trainIdx=commmand[1]-1
    if len(commmand)>2:
        chainIdx=commmand[2]-1
    if commmand[0]==1:
        trains[trainIdx]=trains[trainIdx]|1<<chainIdx
    elif commmand[0]==2:
        trains[trainIdx]=trains[trainIdx]&~(1<<chainIdx)
    elif commmand[0]==3:
        trains[trainIdx]=trains[trainIdx]<<1
        trains[trainIdx]=trains[trainIdx] & ~(1 << 20)
    elif commmand[0]==4:
        trains[trainIdx]=trains[trainIdx]>>1

print(len(set(trains)))

 

 

문제 링크

---

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

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