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