[Silver V] 자리 신청 - 32943

문제 링크

성능 요약

메모리: 152588 KB, 시간: 452 ms

분류

구현, 정렬, 시뮬레이션

제출 일자

2026년 04월 25일 22:04:59

문제 설명

대전과학고등학교에는 선착순으로 자습 좌석을 신청하는 시스템이 있다.

대전과학고등학교 학생은 총 $X$명이며, 각 학생의 학번은 $1$ 이상 $X$ 이하의 서로 다른 정수이다. 각 학생은 $C$개의 좌석 중 하나를 골라 신청할 수 있으며, 각 좌석에는 $1$ 이상 $C$ 이하의 서로 다른 정수 번호가 붙어 있다.

해당 시스템은 다음과 같이 작동한다.

• 각 좌석에는 $1$ 이상 $C$ 이하의 서로 다른 정수 번호가 붙어 있다. 각 좌석은 신청된 좌석 또는 신청되지 않은 좌석 중 하나의 상태를 가지며, 학생들이 좌석을 신청하기 전에 모든 좌석은 신청되지 않은 좌석인 상태이다.
• 만약 학생이 신청한 좌석이 이미 누군가에 의해 신청된 좌석이라면 해당 신청은 무효가 된다. 무효가 되지 않은 신청은 성공한 신청이다.
• 좌석 신청에 성공한 학생은 즉시 신청한 좌석에 배정되며, 학생이 신청한 좌석은 신청된 좌석이 된다.
• 만약 이미 좌석을 배정받은 학생이 다른 좌석 신청에 성공한 경우, 기존에 학생이 배정받았던 좌석은 신청된 좌석에서 신청되지 않은 좌석으로 돌아간다.

하지만 안타깝게도 시스템이 고장이 나는 바람에 좌석 신청이 제대로 되지 않았다. 다행히 서버에는 학생들이 좌석을 신청한 로그가 남아 있다. 각 로그는 학생이 좌석을 신청한 시각 $T$, 학생이 신청한 좌석 번호 $S$, 그리고 학생의 학번 $N$으로 이루어져 있다. $T$가 작을수록 먼저 일어난 신청이다.

여러분은 서버에 남아 있는 로그를 기반으로 최종 신청 결과를 복구하려고 한다. 좌석 신청 로그와 학생 수가 주어질 때, 최종적으로 배정받은 좌석 번호를 출력하는 프로그램을 작성하시오.

입력

첫 번째 줄에는 학생 수 $X$와 좌석의 개수 $C$, 로그의 개수 $K$가 공백으로 구분되어 주어진다. $(1 \leq X, C, K \leq 100 \, 000)$

다음 $K$개의 줄에는 학생이 좌석을 신청한 시각 $T$, 학생이 신청한 좌석 번호 $S$, 그리고 학생의 학번 $N$이 공백으로 구분되어 주어진다. $(0 \leq T \leq 1 \, 000 \, 000 \, 000;$ $1 \leq S \leq C;$ $1 \leq N \leq X)$

모든 로그의 신청 시각 $T$는 서로 다르다. 로그는 시각 순으로 정렬이 되어 있지 않을 수도 있다.

출력

각 줄에 학번의 오름차순으로 각 학생의 학번과 배정받은 좌석 번호를 공백으로 구분하여 출력한다. 단, 좌석을 신청하지 않았거나, 좌석 신청에 한 번도 성공하지 못한 학생은 출력하지 않는다.

---

💡 해결 방법

💻 코드

#https://www.acmicpc.net/status?user_id=softkleenex&problem_id=32943&from_mine=1
 
import sys
input = sys.stdin.readline
 
 
 
 
# 학생수$X$와 좌석의 개수 $C$, 로그의 개수 $K$가 
x, c, k = map(int, input().split())
 
# 다음 $K$개의 줄에는 학생이 좌석을 신청한 시각 $T$, 학생이 신청한 좌석 번호 $S$, 그리고 학생의 학번 $N$이 공백으로 구분되어 주어진다. 
 
list1 =[]
 
for i in range(k):
    list1.append(tuple(map(int, input().split())))
 
list1.sort(key = lambda x :  x[0])
 
# print(*list1, sep = '\n')
 
 
seats = {i : (0, 0) for i in range(1, c + 1)}#죄석번호 : [이용여부, 학번]
stu_seat = {}
 
 
#i는 [시간 좌석번호 학번]
for i in list1:
    seatn = i[1]
    stun = i[2]
    
    if seats[seatn][0] == 1: #고른 좌석에 자리가 있다면
        pass#패스
    else:
        if stun in stu_seat:
            pren_seat = stu_seat[stun]
            seats[pren_seat] = (0, 0)
 
        seats[seatn] = (1, stun)
        stu_seat[stun] = seatn
        
 
ans = []
 
 
for i in range(1, c + 1):
    if seats[i][0] ==  1:
        ans.append([seats[i][1], i])
 
ans.sort()
 
for i in ans:
    print(*i)
 
# 각 줄에 학번의 오름차순으로 각 학생의 학번과 배정받은 좌석 번호를 공백으로 구분하여 출력한다. 단, 좌석을 신청하지 않았거나, 좌석 신청에 한 번도 성공하지 못한 학생은 출력하지 않는다.