문제 풀이에 앞서서 전해드리는 권장사항
- 인터넷 검색은 되도록이면 하지 않도록 합시다.
- 알고리즘만을 제시하는 것도 좋지만 실제로 코딩해 보는걸 권장합니다.
- 댓글에는 완벽한 답을 제시하는 것보단 다른 분들도 풀 수 있도록 힌트를 주는 것을 권장합니다.
이번 문제는 난이도 중하 정도의 문제입니다. 제한 시간은 30분 정도면 적당할 듯 싶네요.
문제
N개의 integers를 가지는 배열 A와 0 <= P < Q < N 을 만족하는 integers P와 Q가 있습니다.
이때 slice(P, Q)란 (A[P] + A[P + 1] + ... + A[Q]) / (Q − P + 1) 를 의미합니다.
예를 들면 배열 A가 다음과 같다고 합시다.
A[0] = 4
A[1] = 2 A[2] = 2 A[3] = 5 A[4] = 1 A[5] = 5 A[6] = 8
이때 slice의 결과는 다음과 같습니다.
- slice (1, 2), whose average is (2 + 2) / 2 = 2;
- slice (3, 4), whose average is (5 + 1) / 2 = 3;
- slice (1, 4), whose average is (2 + 2 + 5 + 1) / 4 = 2.5.
이때 slice의 결과값이 최소가 되도록 하는 P, Q쌍에 대해 P를 리턴하는 함수를 작성하세요.
만약 최소값을 가지는 slice가 여러개일 경우 가장 작은 인덱스 P를 리턴하도록 합니다.
위의 예제의 경우 slice(1, 2)가 최소값을 가지므로 1 을 리턴하게 됩니다.
제약사항은 다음과 같습니다.
Assume that:
- N is an integer within the range [2..100,000];
- each element of array A is an integer within the range [−10,000..10,000].
Complexity:
- expected worst-case time complexity is O(N);
- expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments).
힌트를 드리자면 time complexity가 O(N)이므로 이중 for문을 사용해서 모든 결과를 조회하는 방법을 사용할 수
없습니다. 다른 방식의 접근법을 생각하세요.
