[Programmers] Lv.0 | 공 던지기 | Java

문제

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

 

풀이

1. 수식 측

class Solution {
    public int solution(int[] numbers, int k) {
        // (k - 1) * 2번 이동 후 위치를 numbers 길이로 나눈 나머지가 최종 인덱스
        int index = ((k - 1) * 2) % numbers.length;
        return numbers[index];
    }
}

왜 2씩 곱하는지

 

• k번째 사람이 누구인지 찾기 위함
  • 공은 오른쪽으로 한 명 건너서 던짐 → 매번 2칸 이동
  • 예: 0 → 2 → 4 → 6 → ...
  • 즉, 공을 던질 때마다 인덱스는 +2씩 증가
  • 그래서 2를 곱함

(k - 1) * 2 → 이동한 총 칸 수

• k - 1인 이유
  • 첫 번째 사람(1번)은 공을 받은 게 아니라 시작자니까, 실제 이동은 k - 1번

왜 length로 나누는지 (즉, ... % numbers.length)

• 배열은 원형 구조
• 즉, 끝까지 가면 처음으로 다시 돌아와야 함

인덱스:   0   1   2   3
사람 번호: 1   2   3   4

이동 인덱스:
0 → 2 → 4 → 6 → 8 → ...

→ 배열은 길이 4니까, 4 이상 되면 다시 처음부터 시작
→ 인덱스 4 % 4 = 0
→ 인덱스 6 % 4 = 2
→ 인덱스 8 % 4 = 0

• 그래서 % numbers.length를 해주면 배열 크기를 넘지 않게 순환할 수 있음

 

우리가 구하는 건 몫이 아니라 나머지

 

int index = ((k - 1) * 2) % numbers.length;

• ((k - 1) * 2) → 총 이동한 거리
• % numbers.length → 순환 배열에 맞게 인덱스 조정 (배열을 넘기지 않도록)
• 즉, 몫이 아니라 현재 위치 인덱스를 구하는 것

요약

항목	설명
곱하기 2의 역할	한 명 건너서 공을 던지니까, 인덱스가 한 번에 2씩 증가하는 것을 계산하기 위함
% length 의 역할	원형 배열이기 때문에, 배열의 끝을 넘어갈 경우 다시 처음으로 돌아오기 위함
나머지의 역할	나머지를 구해서 현재 위치(인덱스)를 계산

 

직관 공식 요약

index = ((k - 1) * 2) % numbers.length;

• (k - 1): 던진 횟수
• * 2: 한 번에 두 칸씩 이동
• % numbers.length: 원형 배열 처리 (인덱스가 넘지 않도록)

 

2. 가독성 측면

class Solution {
    public int solution(int[] numbers, int k) {
        int index = 0; // 시작은 1번, 즉 numbers[0]
        
        for (int i = 1; i < k; i++) {
            index += 2; // 오른쪽 한 명 건너서 던지기
            if (index >= numbers.length) {
                index -= numbers.length; // 원형 구조라 넘으면 되돌림
            }
        }

        return numbers[index];
    }
}

 

예제 설명 (numbers = [1, 2, 3], k = 3)

• 시작 index = 0 → numbers[0] = 1
• 첫 번째 던짐: index = 0 + 2 = 2 → numbers[2] = 3
• 두 번째 던짐: index = 2 + 2 = 4 → 초과하므로 index = 4 - 3 = 1 → numbers[1] = 2
• 이제 3번째 던진 사람이 누구냐? → index = 1 → numbers[1] = 2

---

순환 배열

• 배열 끝에 도달하면 다시 처음으로 돌아가는 구조
• 이걸 원형 구조 (circular structure) 라고 함

예: 배열이 [1, 2, 3, 4]이고, 인덱스가 0부터 3까지라고 가정해보자

• 0번째 → 1
• 1번째 → 2
• 2번째 → 3
• 3번째 → 4
• 그 다음? → 다시 0번째로 돌아가야 함 → 순환

왜 나머지가 인덱스가 되는가?

예: 공을 총 6칸 이동했다고 가정해보자. 배열 길이는 4 (즉, numbers.length = 4)

int moved = 6;
int index = moved % 4;  // 결과: 2

• 왜 2번 인덱스가 현재 위치일까요?

나머지가 인덱스가 되는 이유

• 나머지는 배열 내에서의 실제 위치를 나타내기 때문
• 배열의 범위는 0 ~ length - 1 이고, 이동 칸 수가 아무리 커져도 이 범위를 벗어나면 안 되기 때문에,
• 나머지 연산 (%)은 배열 범위 안으로 값을 자동 조절해줌

예: 배열: [1, 2, 3, 4], 길이: 4 (numbers.length = 4)

• 총 이동 칸수 → 실제 위치 (인덱스)

이동 칸수	나머지 (% 4)	배열 인덱스	값
0	0	0	1
1	1	1	2
2	2	2	3
3	3	3	4
4	0	0	1
5	1	1	2
6	2	2	3

• 이동 칸수 % 배열 길이 = 실제 인덱스
• 즉, 배열 밖으로 나가도 걱정 없음, 나머지만 취하면 항상 배열 내 인덱스가 되기 때문