[프로그래머스] 코딩테스트 입문 - 공 던지기
class Solution {
public int solution(int[] numbers, int k) {
int answer = 0;
//k가 1이라면 result는 numbers[0]
//k가 2면 result는 numbers[2]
//k가 3이면 result는 numbers[4]
//1. 그냥 반복문으로 해보자
for (int i = 1; i <= k; i++) {
int result = 2 * (i - 1);
if(result >= numbers.length) {
answer = numbers[result % numbers.length];
}
else answer = numbers[2 * (i - 1)];
}
return answer;
}
}반복문을 써서 문제를 푸는데는 성공했지만, 아무리 생각해도 이게 정답은 아닌 것 같다.
시간복잡도를 중요하게 생각한다면, 이 문제는 반복문이 아닌 다른 방법을 통해 더 빠르게 풀 수 있을 것 같다.
일단, 반복문을 통해 풀었을 경우의 각 테스트 통과 시간을 기록해둔다.
+테스트 47 >통과 (0.05ms, 83.5MB)
위의 문제에서 결국 중요한 사안은 k번째 공을 던졌을 때, 던지는 사람(numbers의 요소)가 누구인지이다.
공은 홀수 번째 사람(요소로서는 짝수 번째)만 던질 수 있으므로, k번째 공을 던지는 사람은 numbers[2 * (k - 1)] 이다.
또 중요한 부분은 '2 * (k - 1)'이 numbers.length를 초과하는 경우다.
2 < numbers.length < 100 이고, 0 < k < 1000 이라는걸 생각하면 대부분의 경우에서 2 * (k - 1)이 numbers.length를 초과할 것이다.(k 가 51이상인 경우 numbers.lenth를 초과함)
간단하게 예시를 들어 생각해보자.
k가 3이고, numbers가 [1,2,3]인 경우, '2 * (k - 1)'(앞으로 result라고 부르겠다.) result = 4, numbers.length = 3 다.
먼저 첫 번째 공을 numbers[0]이 numbers[2]에게 던진다.
두 번째 공은 numbers[2] 가 numbers[4]에게 던져야하지만 numbers.length는 3이므로, numbers[3] = numbers[0]이 되고, numbers[4] = numbers[1]이 된다.
세 번째 공을 던지는 사람은 numbers[4]이고 numbers[4] = numbers[1]이므로 이 예시의 answer는 numbers[1], 즉 2가 된다.
위의 예시에서 구할 수 있는 식은 result > numbers.length인 경우, answer = numbers[result % numbers.length] 이다.
이 식을 활용하여 반복문을 사용하지 않고 문제를 풀어낼 수 있다.
반복문을 사용하지 않고, 풀어낸 코드는 아래와 같다.
class Solution {
public int solution(int[] numbers, int k) {
int answer = 0;
int result = 2 * (k - 1);
if (result > numbers.length) {
answer = numbers[result % numbers.length];
}
else answer= numbers[2 * (k - 1)];
return answer;
}
}이 경우, 각 테스트를 통과하는데 걸린 시간을 알아보자.
반복문 사용 시 테스트 통과 시간 평균 : 3.608695ms
반복문 미사용 시 테스트 통과 시간 평균 : 2.170212ms
예상대로, 테스트 통과 시간을 대폭 줄이는데 성공했다.
많은 사람들이 이 문제를 반복문으로 풀기보다 바로 k번째 공을 던지는 사람을 구해서 풀었을 거라고 생각한다.
아직 내가 코린이기 때문에 반복문을 사용해 푸는 방법을 먼저 생각해냈지만, 그래도 이번 기회로 시간복잡도를 고려하여 코드를 짜는 것이 얼마나 효율적인지 체감해볼 수 있었다.
(그나마 다행인 건 반복문으로 풀면서 이렇게 코딩하는건 너무 비효율적인거 아닌가? 라고 스스로 생각했다는 점이다.)