[Python] 백준/BOJ 28913번: 최애의 팀원 (Silver 3)

💻 Problem

문제 보러 가기

 

김한양은 마지막에 남은 한 명과 같이 해야 한다.

학생들은 모두 자신의 최애의 팀원을 찾기로 했다. 김한양을 제외한 N명의 학생들은 일렬로 선 다음, 가장 앞에 선 학생부터 자신의 최애의 팀원을 한 명씩 찾아간다. 최애의 팀원을 찾는 방법은 다음과 같다.

가장 앞에 선 학생은 뒤돌아 서서 나머지 학생들을 마주본다. 마주보고 있는 학생들 중 가장 앞 사람(즉, 현재 팀원을 찾고 있는 학생과 가장 가까운 학생)이 자신의 팀원이면 둘이 손을 잡고 떠난다. 만약, 자신의 팀원이 아니면 "패스"를 외친다. "패스"를 외치면 팀원 후보 중 가장 앞 사람은 한 바퀴 돌아서 다시 줄의 맨 끝에 서면 된다. 가장 앞에 선 학생의 학번 마지막 두 자리가 X일 때, 이 학생의 팀원은 X−1명의 학생을 패스시키고 만난 X번째 학생이다.

이 과정을 반복하며 학생들은 차례차례 손을 잡고 나갈 것이며, 마지막으로 남은 사람이 김한양의 최애의 팀원이 된다. 김한양의 최애의 팀원을 찾기 위한 여정을 도와주자.

 

💡 Approach

큐에 학생이 한 명만 남을 때까지 큐의 첫 번째 학생이 팀원을 짜면 된다.

 

각 학생은 이니셜과 학번의 마지막 두 자리가 주어진다.

큐의 첫 번째 학생의 학번을 확인하고 해당 학생은 해당 학생의 학번만큼 뒤에 있는 학생과 팀을 맺는다.

-> 큐의 rotate를 활용해 팀원을 바로 찾았다.

 

큐에 마지막에 남은 학생 한 명이 김한양의 팀원이다.

 

✏️ Solution

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

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

while len(queue) > 1:
    front = queue.popleft()
    queue.rotate(1 - int(front[1]))
    queue.popleft()

print(queue[0][0])

시간복잡도: O(nk)

학생 수가 n이고 학번을 k라고 할 때, 1/2 * n * k이다.

popleft()를 두 번하므로 while 문을 1/2 * n번 반복하고, rotate()를 k번 하기 때문이다.