[파이썬/python] 백준 29813- 최애의 팀원

문제

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

---

문제 설명

1. 일렬로 서있는 N명의 학생들이 존재한다.
2. 가장 앞에 선 학생부터 최애의 팀원을 찾는다.
   1. 가장 앞에 선 학생은 뒤를 돌아보며 맞은편에 있는 학생이 자신의 팀원이 아니라면 해당 학생은 맨 뒤로 이동한다.
   2. 가장 앞의 선 학생의 학번이 X일 때 해당 학생의 팀원은 X-1명을 패스시키고 만난 X번째 학생이다.
3. 마지막으로 남은 사람이 김한양의 최애의 팀원이다.
4. 김한양의 최애의 팀원을 출력한다.

 

---

풀이

마주본 학생이 팀원이 아닐 경우 맨 뒤로 가게되며,

앞에 있는 학생들이 계속해서 뒤로 이동해서 다른 학생들은 앞으로 밀리는 구조가 반복된다.

따라서 선입선출인 Queue 자료구조를 이용하여 팀원을 구한다.

1. 학번 - 1 만큼 뒤의 학생을 패스한다.
2. 패스가 끝난 후 가장 앞의 학생이 현재 기준 학생의 팀원이므로 popleft() 한다.
3. queue의 크기가 1이 되었을 때 남은 학생 1명이 김한양의 팀원이므로, 반복문을 탈출한 후 해당 학생을 출력한다.

---

코드

import sys
from collections import deque
input = sys.stdin.readline

N = int(input())
queue = deque(input().split() for _ in range(N))

while len(queue) > 1:
    name, num = queue.popleft()
    num = -(int(num)-1) // 패스할 횟수 결정, 왼쪽으로 queue가 밀려야 하므로 음수.
    queue.rotate(num) // -num만큼 학생들을 패스한다..
    queue.popleft() // 해당 위치(x번째)의 학생이 팀원이다.
partner = queue.popleft()
print(partner[0])

---

시간복잡도

• queue의 삽입,삭제 시간복잡도는 $O(1)$이다.
• 총 N명의 학생이 존재하므로 약 $O(N)$의 시간복잡도가 소요된다.
• 학번을 K라고 했을 때 rotate의 시간복잡도는 $O(K)$이다.
• 따라서 총 시간복잡도는 약 $O(N*K) = O(10^3 * 99) = O(10^5)$이다.