codility Lesson5 - MinAvgTwoSlice

코드

1차 시도
시간복잡도: O(N**2) -> Large Case TIMEOUT ERROR

// you can use includes, for example:
// #include <algorithm>

// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;

 int solution(vector<int> &A) {
     // write your code in C++14 (g++ 6.2.0)

     vector<int> S;
     double min = (double)(A[0] + A[1] + 20000) / 2;
     int now = A[0]+A[1] + 20000;
     int answer = 0;
     S.push_back(A[0] + 10000);
     S.push_back(A[0]+A[1] + 20000);
     // cout << min << endl;
     for(int i=2;i<A.size();i++) {
         now += A[i] + 10000;
         S.push_back(now);
         if(min > now / i) {
             min = (double)now / i;
             answer = 0;
         }
         for(int j=0;j<i-1;j++) {
             double cal = (double)(now-S[j]) / (i-j);
             // cout << cal << " " << i << " " << j << endl;
             if(min > cal) {
                 min = cal;
                 answer = j + 1;
             }
         }
     }

     return answer;
 }

시간 초과와 각종 코딜리티 버그를 많이 발견한 코드이다...ㅠㅠ

2차 시도
시간복잡도: O(N)

// you can use includes, for example:
// #include <algorithm>
#include <string>
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;

int solution(vector<int> &A) {
    // write your code in C++14 (g++ 6.2.0)

    double min = 999999;
    int answer = 0;
    for(int i=0;i<A.size()-1;i++) {
        if( min > (double)(A[i] + A[i+1] + 20000) / 2) {
            min = (double)(A[i] + A[i+1] + 20000) / 2;
            answer = i;
        }
    }

    for(int i=0;i<A.size()-2;i++) {
        if( min > (double)(A[i] + A[i+1] + A[i+2] + 30000) / 3) {
            min = (double)(A[i] + A[i+1] + A[i+2] + 30000) / 3;
            answer = i;
        }
    }

    return answer;
}

아는 형들과 디스코드 하면서 풀다가 한명이 제안한 아이디어로 해결했다.. 역시 갓이었다.

풀이 및 소감

수학적으로 접근해야하는 문제였다... 핑계를 대자면 Prefix Sums 파트여서 부분합을 계속 활용하려고 했다. 위의 풀이가 부분합을 활용한 건지 모르겠다. 그리고 코딜리티에서 버그를 많이 발겼했다. 푼지 조금 시간이 지나서 헷갈리는데 음수에서 -2.7이 -3.5보다 작다고 나오는 식의 음수, 소수에서 문제가 많이 발생했다... 저번에 코딜리티 기술 팀과 한참 얘기했던 적이 있어서 좀 지쳐서 이번에는 메일을 안 보냈는데 나중에 또 이런 문제가 있거나 정리를 해야겠다고 싶으면 한번에 모아서 보내봐야겠다ㅠㅠㅠ

---

참고 사이트

• [Codility] MinAvgTwoSlice 문제 풀이
• [코딜리티] MinAvgTwoSlice (javascript)