[프로그래머스 입문][자바] 볼 던지기

❓문제설명

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

프로그래머스

 

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

공은 1번부터 던지며 오른쪽으로 한 명을 건너뛰고 그 다음 사람에게만 던질 수 있습니다.

친구들의 번호가 들어있는 정수 배열 numbers와 정수 K가 주어질 때, k번째로 공을 던지는 사람의 번호는 무엇인지 return 하도록 solution 함수를 완성해보세요.

---

제한사항

• 2 < numbers의 길이 < 100
• 0 < k < 1,000
• numbers의 첫 번째와 마지막 번호는 실제로 바로 옆에 있습니다.
• numbers는 1부터 시작하며 번호는 순서대로 올라갑니다.

---

입출력 예

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

 

---

 

입출력 예 #1

• 1번은 첫 번째로 3번에게 공을 던집니다.
• 3번은 두 번째로 1번에게 공을 던집니다.

입출력 예 #2

• 1번은 첫 번째로 3번에게 공을 던집니다.
• 3번은 두 번째로 5번에게 공을 던집니다.
• 5번은 세 번째로 1번에게 공을 던집니다.
• 1번은 네 번째로 3번에게 공을 던집니다.
• 3번은 다섯 번째로 5번에게 공을 던집니다.

입출력 예 #3

• 1번은 첫 번째로 3번에게 공을 던집니다.
• 3번은 두 번째로 2번에게 공을 던집니다.
• 2번은 세 번째로 1번에게 공을 던집니다.

---

🔍문제해석

어떤걸 풀어야 할까?

1. 친구들이 둥글게 앉아있다고 가정하고, 공을 던질때 바로 옆사람이 아닌 한 사람 건너서 전달한다. 그럴때 k번째로 공을 잡은 사람을 누구인지 구하라. 

2. 무조건 1번부터 시작한다.

3. k번 공을 던진게 아니다.

---

🧐문제풀이

• 문제 풀이 구상

array가 사실 원형으로 있으니 배열은 주어진 length로만 끝나는게 아니라 무한이다.

공을 length이상으로 던지고 받을 걸 가정하여 가상의 원소를 더 만들어서 생각해보았다.

최소 k*2의 원소가 필요하고, array.length * n 까지 가상의 원소를 생성하도록 하였다.

그 곳에 k번째 공을 잡고있는 항목을 get하여 정답을 구할 수 있다.

---

！제출코드

1. 공을 한사람 걸러 던지기 때문에 k*2 를 구해서 계산할 범위를 어림잡음
2.  k * 2 가 친구들의 수보다 더 크면 list를 하나 생성하고 그곳에 n바퀴 이상 돌아가는 친구들을 넣는다.
3. 배열로 주어진 친구들을 원형으로 가정하고 계산하기 위해 친구수 * ((k*2)/친구수 + 1)까지 반복문을 수행한다. (몇바퀴를 돌지 계산하는것) 
4. 주어진 친구의 수를 그대로 쓰기 위해 i%numbers.length를 인덱스로 사용한다. 
5. list에서 k + (k-2) 째의 원소를 정답으로 리턴한다.
6. k * 2 가 친구들의 수보다 더 크지않다면 array에서 k + (k-2) 째의 원소를 정답으로 리턴한다.

import java.util.*;

class Solution {
    public int solution(int[] numbers, int k) {
    
        int answer = 0;
        // (1)
        List<Integer> list = new ArrayList<>();
        // (2)
        if((k * 2) > numbers.length){
        // (3)
        for(int i = 0; i < numbers.length * ((k * 2) / numbers.length + 1); i++){
                // (4)
                list.add(numbers[i % numbers.length]);
           
            }
            // (5)
            answer = list.get(k + (k -2));
            
        }else {
            // (6)
            answer = numbers[k + (k -2)];
        }
        
        return answer;
    }
}

 

---

➕ 참고할 만한 다른 풀이

내가 구상한대로 코드가 잘 짜여졌고, 문제도 통과했지만

for문의 범위를 구하는 것도 그렇고, 리스트나 array에서 값을 가져오는 것도 그렇고 뭔가 더 깔끔하게 풀 수 있는 방법이 있지않을까 하고 더 찾아보았다. 

 

https://school.programmers.co.kr/learn/courses/30/lessons/120843/solution_groups?language=java

프로그래머스

 

1 ) 내가 궁극적으로 원한 queue를 이용한 풀이 

import java.util.*;

class Solution {
    public int solution(int[] numbers, int k) {
        int answer = 0;

        Queue<Integer> queue = new LinkedList<>();
        for(int num : numbers) queue.add(num);

        int cnt = 1;
        while(cnt !=k){
            queue.add(queue.poll());
            queue.add(queue.poll());
            cnt++;
        }
        answer = queue.poll();
        return answer;
    }
}

 

한사람 걸러 그 다음사람에게 공이 가기때문에 두번 poll하고 add하는 과정을 거쳐

k번째를 찾아간다.

 

2 ) 깔끔한 코드 

class Solution {
    public int solution(int[] numbers, int k) {
        return (k-1)*2 % numbers.length+1;
    }
}

 

이건 어떻게 짜시는거야..?  이해도 안된다..