문제
머쓱이는 친구들과 동그랗게 서서 공 던지기 게임을 하고 있습니다. 공은 1번부터 던지며 오른쪽으로 한 명을 건너뛰고 그다음 사람에게만 던질 수 있습니다. 친구들의 번호가 들어있는 정수 배열 numbers와 정수 K가 주어질 때, k번째로 공을 던지는 사람의 번호는 무엇인지 return 하도록 solution 함수를 완성해보세요.
- 제한사항
- 2 < numbers의 길이 < 100
- 0 < k < 1,000
- numbers의 첫 번째와 마지막 번호는 실제로 바로 옆에 있습니다.
- numbers는 1부터 시작하며 번호는 순서대로 올라갑니다.
풀이
- 오답
if문으로 경우의 수를 나누는 순서에 따라 1통23불, 12통3불, 1불23통 아주 천차만별로 갈렸다. 아래와 같은 순서로 겨우 테스트케이스를 통과했는데, 코드를 제출하니 47개 중 2개를 통과하지 못했다 ㅜㅜ
추측하건대 통과를 하지 못하는 게 아니라 시간이 초과되는 걸로 보아서 k의 범위가 1,000 미만까지로 큰 편이라 for문 사용 시 시간이 오래 걸리는 듯 보였다. 따라서 다른 방법을 사용해 보기로 했다.
class Solution {
public int solution(int[] numbers, int k) {
int answer = 0;
int idx = 0;
for(int i=0; i<numbers.length; i+=2){
if(i == numbers.length - 1){
i = 1;
idx++;
}
idx++;
if(idx == k){
answer = numbers[i];
break;
}
if(i == numbers.length - 2){
i = 0;
idx++;
}
}
return answer;
}
}- 정답
이 문제를 제일 처음 봤을 때 생각했던 while문을 이용해 보기로 했다. 우선 필요한 변수들을 생성해 주었다. numbers.length가 아닌 k를 기준으로 삼고, k와 횟수를 담을 변수 cnt가 같아지는 순간 반복문을 빠져나오도록 k > cnt를 조건문으로 삼았다.
그리고 공을 받은 사람의 인덱스가 될 변수 idx는 반복문을 돌 때마다 2씩 증가하도록 해주되(다다음 사람에게 공 넘기기), 길이와 같아지거나 넘어설 경우 idx를 길이로 나눈 나머지 값을 idx에 대입해 주었다.
위에서 말한 idx %= numbers.length;를 생각해 내는 것까지가 시간이 엄청 걸렸다. 어떻게 하면 길이가 짝수이건 홀수이건 상관 없이 모든 경우에 들어맞도록 조건을 간편화 할 수 있을까 고민했고 주어진 길이에 못 담아서 넘쳐 흐른 값이라고 생각했을 때 이게 나머지라는 결론을 얻게 되었다.
ex) numbers : [1,2,3,4,5,6], k : 5 → 1 - 3 - 5 - 7**
**idx %= 6 = 1번 인덱스, 즉 2로 이동하게 됨
class Solution {
public int solution(int[] numbers, int k) {
int answer = 0;
int cnt = 0;
int idx = 0;
while (k > cnt) {
if (idx >= numbers.length) {
idx %= numbers.length;
}
answer = numbers[idx];
idx += 2;
cnt++;
}
return answer;
}
}결과
