[백준 2024/02/14] 9863번 Calling All Programmers

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

9863번: Calling All Programmers

 

1. 접근 방법

이번 문제는 문제를 푸는 것보다 문제를 해석 하는데 더 많은 시간을 쓴 것 같다.

 

간단히 문제 해석을 적어보자면 다음과 같다.

 

처음에는 해당 문제를 queue로 접근했다.

앞에서 하나씩 pop 하고 뒤에서 append를 하는 것을 반복하는 것을 생각하고 문제를 풀었다. 7 번째는 출력해주고 뒤에 append하지 않는 식으로 구성하였다.

예제 코드는 출력이 되었으나, 막상 백준에 넣어봤을 때 '런타임 에러' 가 발생하였다. 어떤 종류인 런타임 에러인지 알려주지 않아 이것저것 찾아보다가, index로 다시 접근하기로 마음 먹었다. 아직도 왜 런타임 에러가 발생한 지는 모르겠다.

 

아래는 런타임 에러가 발생한 코드이다. ** 수정 : PyPy3 가 아니라, python3로 제출하니 맞았다.

import queue


while True:
    n, m, k = map(int, input().split())
    if n==0 and m ==0 and k ==0:
        break
    q = queue.Queue()
    for i in range(1, n+1, 1):
        q.put(i)

    count = 0
    while not q.empty() and count < k:
        for _ in range(m-1):
            q.put(q.get())
        popped = q.get()
        count += 1

    print(popped)

 

이제 index로 접근하는 방법에 대해서 적어보도록 하겠다.

예제 입력 

10 7 5

 

예제 출력 

3

 

을 예시로 적어보겠다.

일단 list를 구성해주었다.

list[0] = 1

list[1] = 2

list[2] = 3

...

list[9] = 10

 

이렇게 구성해주었다.

idx        0	1	2	3	4	5	6	7	8	9
value     1	2	3	4	5	6	7	8	9	10

 

이후 없어지는 idx의 패턴은 다음과 같다.

현재 (idx + (m - 1)) % len(list)

현재 idx 에서 6을 이동하고, 만약 list 의 길이를 넘어서 이동했을 경우를 대비해서 list의 길이로 나머지를 구해준다.

여기서 len(list) 를 반복문 마다 다시해주는 이유는, 반복문 마다 list에서 하나씩 pop이 되기 때문이다. 

즉, list의 길이가 유동적으로 변하기 때문이다. 

 

7을 더하는 것이 아니라, 6을 더하는 것은, pop이 된 곳에서 부터 세기를 시작해야하기 때문이다. 

 

0 + 6 % 10 = 6

6 + 6 % 9 = 3

3 + 6 % 8 = 1

1 + 6 % 7 = 0

0 + 6 % 6 = 0

 

pop 이 되면서 idx 값이 유동적으로 바뀌게 됨을 이해해야 한다.

 

2. 코드

def find_kth_caller(n, m, k):
    callers = list(range(1, n + 1))
    index = 0

    for i in range(k-1):
        index = (index + m - 1) % len(callers)
        callers.pop(index)

    final_index = (index + m - 1) % len(callers)
    return callers[final_index]

while True:
    n, m, k = map(int, input().split())
    if n == 0 and m == 0 and k == 0:
        break
    print(find_kth_caller(n, m, k))