15787번: 기차가 어둠을 헤치고 은하수를
입력의 첫째 줄에 기차의 수 N(1 ≤ N ≤ 100000)과 명령의 수 M(1 ≤ M ≤ 100000)가 주어진다. 이후 두 번째 줄부터 M+1번째 줄까지 각 줄에 명령이 주어진다.
www.acmicpc.net
문제
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번째 줄까지 각 줄에 명령이 주어진다.
출력
은하수를 건널 수 있는 기차의 수를 출력하시오.
코드
deque 이용
import sys
input = sys.stdin.readline
from collections import deque
n, m = map(int, input().split())
train = [deque([0] * 20) for _ in range(n)] # 각각 20개의 좌석이 있는 n개의 기차
for _ in range(m):
cmd = list(map(int, input().split()))
if cmd[0] == 1:
if train[cmd[1]-1][cmd[2]-1] == 0:
train[cmd[1]-1][cmd[2]-1] = 1 # 승차
elif cmd[0] == 2:
if train[cmd[1]-1][cmd[2]-1] == 1:
train[cmd[1]-1][cmd[2]-1] = 0 # 하차
elif cmd[0] == 3:
train[cmd[1]-1].rotate(1)
train[cmd[1]-1][0] = 0
else:
train[cmd[1]-1].rotate(-1)
train[cmd[1]-1][19] = 0
lst = set()
for i in range(n):
if tuple(train[i]) in lst: # 이미 목록에 존재하는 기록
continue
lst.add(tuple(train[i]))
print(len(lst))
- 각 기차의 승객 탑승 정보를 deque에 저장
- 원소의 값이 0이면 승객이 없고 1이면 승객이 있는 것.
- 3, 4번 명령은 deque의 rotate 함수를 이용하여 처리.
비트마스크 이용
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
train = [0] * (n+1)
for _ in range(m):
cmd = list(map(int, input().split()))
if cmd[0] == 1:
train[cmd[1]] |= (1 << (cmd[2]-1))
elif cmd[0] == 2:
train[cmd[1]] &= ~(1 << (cmd[2]-1))
elif cmd[0] == 3:
train[cmd[1]] = train[cmd[1]] << 1
train[cmd[1]] &= ~(1 << 20)
else:
train[cmd[1]] = train[cmd[1]] >> 1
print(len(set(train[1:])))
다른 풀이를 찾아보니 비트마스크를 이용해서 한 풀이들도 있길래 비트마스크로도 풀이해보았다. 위의 풀이보다 시간과 공간 효율성면에서 훨씬 효율적이다.
'문제풀이 > 구현' 카테고리의 다른 글
[Python/파이썬] 백준 16918번 봄버맨 (0) | 2023.02.25 |
---|---|
[Python/파이썬] 백준 16926번 배열 돌리기 1 (0) | 2023.02.24 |
[Python/파이썬] 백준 17276번 배열 돌리기 (0) | 2023.02.23 |
[Python/파이썬] 백준 21611번 마법사 상어와 블리자드 (0) | 2023.02.23 |
[Python/파이썬] 백준 4396번 지뢰 찾기 (0) | 2023.02.20 |
15787번: 기차가 어둠을 헤치고 은하수를
입력의 첫째 줄에 기차의 수 N(1 ≤ N ≤ 100000)과 명령의 수 M(1 ≤ M ≤ 100000)가 주어진다. 이후 두 번째 줄부터 M+1번째 줄까지 각 줄에 명령이 주어진다.
www.acmicpc.net
문제
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번째 줄까지 각 줄에 명령이 주어진다.
출력
은하수를 건널 수 있는 기차의 수를 출력하시오.
코드
deque 이용
import sys input = sys.stdin.readline from collections import deque n, m = map(int, input().split()) train = [deque([0] * 20) for _ in range(n)] # 각각 20개의 좌석이 있는 n개의 기차 for _ in range(m): cmd = list(map(int, input().split())) if cmd[0] == 1: if train[cmd[1]-1][cmd[2]-1] == 0: train[cmd[1]-1][cmd[2]-1] = 1 # 승차 elif cmd[0] == 2: if train[cmd[1]-1][cmd[2]-1] == 1: train[cmd[1]-1][cmd[2]-1] = 0 # 하차 elif cmd[0] == 3: train[cmd[1]-1].rotate(1) train[cmd[1]-1][0] = 0 else: train[cmd[1]-1].rotate(-1) train[cmd[1]-1][19] = 0 lst = set() for i in range(n): if tuple(train[i]) in lst: # 이미 목록에 존재하는 기록 continue lst.add(tuple(train[i])) print(len(lst))
- 각 기차의 승객 탑승 정보를 deque에 저장
- 원소의 값이 0이면 승객이 없고 1이면 승객이 있는 것.
- 3, 4번 명령은 deque의 rotate 함수를 이용하여 처리.
비트마스크 이용
import sys input = sys.stdin.readline n, m = map(int, input().split()) train = [0] * (n+1) for _ in range(m): cmd = list(map(int, input().split())) if cmd[0] == 1: train[cmd[1]] |= (1 << (cmd[2]-1)) elif cmd[0] == 2: train[cmd[1]] &= ~(1 << (cmd[2]-1)) elif cmd[0] == 3: train[cmd[1]] = train[cmd[1]] << 1 train[cmd[1]] &= ~(1 << 20) else: train[cmd[1]] = train[cmd[1]] >> 1 print(len(set(train[1:])))
다른 풀이를 찾아보니 비트마스크를 이용해서 한 풀이들도 있길래 비트마스크로도 풀이해보았다. 위의 풀이보다 시간과 공간 효율성면에서 훨씬 효율적이다.
'문제풀이 > 구현' 카테고리의 다른 글
[Python/파이썬] 백준 16918번 봄버맨 (0) | 2023.02.25 |
---|---|
[Python/파이썬] 백준 16926번 배열 돌리기 1 (0) | 2023.02.24 |
[Python/파이썬] 백준 17276번 배열 돌리기 (0) | 2023.02.23 |
[Python/파이썬] 백준 21611번 마법사 상어와 블리자드 (0) | 2023.02.23 |
[Python/파이썬] 백준 4396번 지뢰 찾기 (0) | 2023.02.20 |