[C++] 삼성 SDS KOITP 오래된 계산기 (시간초과)

문제링크 : https://koitp.org/problem/SDS_TEST_CALCULATOR

[삼성 SDS 대학생 알고리즘 특강 사전 테스트 B Type 3번 문제]

시간초과로 실패했던 문제이다.

1. 일단 정렬한다.

2. 앞의 두 숫자(최소값)을 더하고 더한 숫자를 뒷쪽에 끼워놓는다.

3. 반복

삭제와 삽입이 빈번하게 일어나기 때문에 STL vector를 사용하면 시간이 매우 오래걸리게 된다.

또한, 매 loop 실행시마다 삽입의 적절한 위치를 찾기 위해 for문을 돌리기 때문에 O(N^2)이 되겠다.

답은 맞은듯하나 시간초과로 실패하였다. 우선순위 큐를 사용하면 될 것 같기도 한데 아직 이것도 모르겠다.

일반 배열과 vector를 제외한 다른 자료구조에 대한 학습이 부족하여 여기까지가 한계인듯하다.

추후에 자료구조 심화학습을 하게 된다면 다시 한번 살펴봐야겠다.

// KOITP_SDS_Btype_03
#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
    // freopen("../input.txt", "r", stdin);
    ios_base::sync_with_stdio(false);
    int T;
    cin >> T;
    for (int t = 1; t <= T; t++) {
        int n, result = 0;
        cin >> n;
        vector<int> num(n);
        for (int i = 0; i < n; i++)
            cin >> num[i];
        sort(num.begin(), num.end());
        while (true) {
            int tmp = num[0] + num[1];
            num.erase(num.begin(), num.begin()+2);
            result += tmp;
            if (num.empty())
                break;
            int cnt = 0;
            for (int i = 0; i < num.size(); i++) {
                if (tmp > num[i]) cnt++;
                else break;
            }
            num.insert(num.begin() + cnt, tmp);
        }
        cout << "#" << t << " " << result << "\n";
    }
    return 0;
}