프로그래머스 입문 120843 공 던지기

2026. 07. 12

문제

매개변수로 정수 배열 numbers와 정수 k가 주어진다.
공은 numbers[0]에 해당하는 사람부터 시작해 한 사람을 건너뛰며 오른쪽으로만 전달된다.
이때 k번째로 공을 던지는 사람의 번호를 구하세요.

numbers	k	result
[1, 2, 3, 4]	2	3
[1, 2, 3, 4, 5, 6]	5	3
[1, 2, 3]	3	2

풀이

반복문으로 패스를 하나씩 처리하기

#include <stdlib.h>

int solution(int numbers[], size_t numbers_len, int k)
{
    int thrower_index = 0;

    for (int i = 0; i < k - 1; i++)
    {
        thrower_index = (thrower_index + 2) % numbers_len;
    }

    return numbers[thrower_index];
}

k번째로 공을 던지는 사람은 k - 1번째 전달에서 공을 받은 사람이다.
그래서 문제를 k - 1번째에서 공을 받는 사람을 구하는 문제로 생각할 수도 있다.
다만 문제와 일관성을 갖추기 위해 공을 던지는 사람에 집중해서 thrower_index라는 이름을 사용했다.

반복문 1회 차를 패스 1회로 보고 총 k - 1번 반복하므로 시간 복잡도는 O(k)이다.
처음 공을 가진 numbers[0]에 해당하는 사람은 이미 첫 번째로 공을 던지는 사람이다.
따라서 k번째로 공을 던지는 사람까지는 이후 k - 1번의 패스만 필요하다.

공은 한 사람을 건너뛰며 오른쪽으로만 전달되므로 인덱스를 2만큼 증가시킨다.
배열의 범위를 초과하면 나머지 연산자로 다시 유효한 인덱스로 만든다.

수식으로 바로 계산하기

#include <stdlib.h>

int solution(int numbers[], size_t numbers_len, int k)
{
    int thrower_index = (2 * (k - 1)) % numbers_len;
    return numbers[thrower_index];
}

이전 풀이는 패스를 반복문으로 하나씩 처리했다.
반면 인덱스 변화 규칙을 이용하면 반복문 없이 한 번의 수식으로 계산할 수 있으므로 시간 복잡도는 O(1)이다.