알고리즘 시간 초과 해결

 

프로그래머스 문제를 풀던 도중 아래의 풀이에서 시간 초과가 발생했다.

 

가능성은 2가지라고 생각했다.

1. O(nlog n)이 소요되는 sort() 함수
2. O(n²)이 소요되는 while 루프 부분

 

while 루프에서 O(n²)이 소요되는 이유는 다음과 같다.

• while 루프의 반복 횟수가 score 벡터의 크기에 종속적이므로 O(n)
• vector.erase()에서 앞 부분이 삭제되면서 뒷 부분을 당겨오게 되므로 O(n)

 

int solution(int k, int m, vector<int> score)
{
    int answer = 0;

    sort(score.rbegin(), score.rend());

    while (m <= score.size())
    {
        answer += score[m - 1] * m;

        score.erase(score.begin(), score.begin() + m);
    }

    return answer;
}

 

나는 사과를 삭제하는 부분을 개선해보기로 했다.

 

생각해보니 가격을 계산한 사과를 굳이 삭제하지 않고 인덱스를 이용해 건너 뛰면서 계산해도 됐다.

 

사과를 점수에 따라 내림차순으로 정렬하여 m개씩 건너뛰며 계산하여 시간 초과를 해결했다.

• 이때 while 루프는 O(n) 복잡도를 갖는다.

 

삭제를 하더라도 점수가 큰 사과를 뒤에 놓고 뒤에서부터 사과를 삭제해나가면 시간 초과가 발생하지 않을 것이다.

 

int solution(int k, int m, vector<int> score)
{
    int answer = 0;
    size_t size = score.size();

    sort(score.rbegin(), score.rend());

    for (int i = m - 1; i < size; i += m)
        answer += score[i] * m;

    return answer;
}

 

좀 더 개선해보고자 가장 높은 점수의 사과부터 차례대로 확인한다는 점에서 아이디어를 얻어 우선순위 큐를 사용해보기로 했다.

 

참고로, 우선순위 큐 생성 시에 목록을 전달하여 초기화하면 O(n) 시간에 최대 힙을 생성할 수 있다.

 

아래의 while 루프는 O(nlog n) 복잡도를 갖는다.

• while 루프의 반복 횟수가 우선순위 큐의 크기에 종속적이므로 O(n)
• for 루프는 큐의 크기와 관계 없는 상수이므로 O(1)
• priority_queue.pop()에서 하향식 재구성이 일어나면서 O(log n)

 

int solution(int k, int m, vector<int> score)
{
    int answer = 0;
    priority_queue<int> prque(score.begin(), score.end());

    while (m <= prque.size())
    {
        int min_score = 0;

        for (int i = 0; i < m; ++i)
        {
            min_score = prque.top();
            prque.pop();
        }

        answer += min_score * m;
    }

    return answer;
}

 

아쉽지만 벡터를 정렬한 후 순회하는 방식이 시간과 공간 모두에서 더 좋은 성능을 냈다.

 

어느 정도 예상하기는 했지만, n번 원소를 빼며 하향식 재구성을 하는 것보다는 1번 정렬하는 것이 더 빠를 것이다.

 

벡터를 정렬하여 사용한 결과(좌), 우선순위 큐를 사용한 결과(우)