[programmers] '공 던지기' 문제 해설 및 정답코드

✅ 문제 출처

https://school.programmers.co.kr/learn/courses/30/lessons/120843

 

 

✅ 문제 설명

머쓱이는 친구들과 동그랗게 서서 공 던지기 게임을 하고 있습니다.

• 공은 오른쪽으로 한 명을 건너뛰고 그다음 사람에게만 던질 수 있습니다.
• k번째로 공을 던지는 사람의 번호를 구해야 합니다.
• 친구들의 번호가 들어있는 정수 배열 numbers와 k가 주어집니다.
• numbers 배열은 순서대로 증가하는 번호를 가지며, 마지막 번호 다음에는 첫 번째 번호가 이어집니다.
• 즉, 원형 구조(순환 리스트)에서 공이 움직이는 패턴을 찾아야 합니다.

---

 

 

🔍 입출력 예시

numbers k 결과

[1, 2, 3, 4]	2	3
[1, 2, 3, 4, 5, 6]	5	3
[1, 2, 3]	3	2

---

 

 

🛠 문제 해결 과정

 

1️⃣ 공 던지는 규칙 분석

1. 공을 **처음 시작하는 사람은 1번**입니다.
2. 공을 던질 때마다 오른쪽으로 한 명을 건너뛰고 던집니다.
3. k번째로 공을 던지는 사람이 누구인지 찾습니다.

예제 1: [1, 2, 3, 4], k = 2

1. 1번 → 3번 (1번째 던짐)
2. 3번 → 1번 (2번째 던짐, 정답)

🔹 결과: 3

예제 2: [1, 2, 3, 4, 5, 6], k = 5

1. 1 → 3
2. 3 → 5
3. 5 → 1
4. 1 → 3
5. 3 → 5 (정답)

🔹 결과: 3

예제 3: [1, 2, 3], k = 3

1. 1 → 3
2. 3 → 2
3. 2 → 1 (정답)

🔹 결과: 2

---

 

 

2️⃣ 문제 해결을 위한 패턴 분석

공 던지기 순서의 인덱스를 찾는 패턴을 발견할 수 있습니다.

• 1번째 던지기: index = 0 + 2
• 2번째 던지기: index = 2 + 2
• 3번째 던지기: index = 4 + 2
• ...

즉, 2 * (k - 1) 번째 인덱스를 찾으면 k번째 던질 사람이 누구인지 알 수 있습니다.

하지만, 리스트의 끝을 넘어서면 처음으로 돌아가야 합니다!

• 이를 위해 mod 연산(%)을 사용하면 리스트를 순환할 수 있습니다.
• numbers[(2 * (k - 1)) % len(numbers)]를 사용하면 리스트 범위를 벗어나지 않고 원형 구조를 유지할 수 있습니다.

---

 

 

🔥 최적화된 해결 방법

def solution(numbers, k):
    return numbers[(2 * (k - 1)) % len(numbers)]

 

📌 코드 설명

1. 2 * (k - 1):
   • k번째 던질 때까지 인덱스를 +2씩 증가한 총 이동 거리 계산
2. % len(numbers):
   • 리스트의 끝을 넘어가면 처음으로 돌아가기 위해 순환 구조 적용
3. numbers[...]:
   • 최종적으로 해당 인덱스에 위치한 번호를 반환

---

 

 

📌 실행 예제 및 결과

print(solution([1, 2, 3, 4], 2))  # 3
print(solution([1, 2, 3, 4, 5, 6], 5))  # 3
print(solution([1, 2, 3], 3))  # 2

✅ 출력 결과:

3
3
2

---

 

 

🔑 핵심 정리

개념 설명

리스트 순환	% len(numbers)를 사용하여 리스트를 초과하면 처음으로 돌아감
2칸씩 이동	2 * (k - 1)를 사용하여 공이 던져지는 순서 계산
최적화된 접근법	반복문 없이 한 줄의 수식으로 해결 가능
원형 리스트	공이 리스트 끝을 넘어가면 다시 첫 번째로 돌아옴
시간 복잡도	O(1)로 빠르게 해결 가능 (반복문 사용 X)