문제
https://www.acmicpc.net/problem/31797
풀이
- 게임을 시작한 사람이 아파트의 층수
N을 정한다. - 게임의 모든 참가자는 자신의 두 손을 다른 사람과 겹치지 않는 높이로 뻗어 모든 참가자의 두 손이 서로 쌓이도록 한다.
- 가장 아래에 있는 손을 빼 쌓여있는 손 가장 위에 쌓는다.
- 위의 과정을
N번 반복한다.j번째로 쌓은 손이 층이 된다. j층을 쌓는 참가자가 술을 마시고 게임이 종료된다.
실제 술게임을 진행하는 것을 떠올려서 구현하면 쉽게 해결할 수 있습니다.
손을 입력된 순서대로 쌓았다고 가정했을 때, 맨 아래에 있는 손부터 차례대로 가장 위로 올리면 됩니다.
이를 처음 올리면 1층, 2번째로 올리면 2층, 3번째로 올리면 3층, ...
deque의 rotate()함수를 사용하면 이를 쉽게 구현할 수 있습니다.
물론 배열로 pop(0)과 append()를 이용하여서도 구현할 수 있습니다.
for i in range(1,m+1): # 번호 부여를 인덱스를 사용할 것이라 1부터 시작
a,b = map(int,input().split()) # 왼손, 오른손이 위치할 좌표
# 손의 위치와 그 손의 주인을 같이 입력
queue.append([a,i])
queue.append([b,i])가장 아래에 있는 손부터 위로 올려야하기 때문에 첫번째 원소값을 기준으로 정렬해줍니다.
queue = deque(sorted(queue))정렬이 됐다면 이제 손을 아래부터 위로 올리기 시작하면 됩니다.
0번 인덱스의 값을 가장 뒤로 옮겨주는 행위를 총 n번 반복하면 됩니다.
for _ in range(n):
queue.rotate(-1)이렇게 n번 반복하게 되면 가장 뒤에 있는 손의 주인이 술을 마시게 됩니다. 🥳
print(queue[-1][1]) # n층에 위치한 사람코드
from collections import deque
import sys
input = sys.stdin.readline
n,m = map(int,input().split())
queue= deque()
for i in range(1,m+1):
a,b = map(int,input().split())
queue.append([a,i])
queue.append([b,i])
queue = deque(sorted(queue))
for _ in range(n):
queue.rotate(-1)
print(queue[-1][1])