백준 11501번:주식

11501번: 주식

이번 문제는 어렵게 생각해서 그런지 시간이 생각보다 오래 걸렸다.

총 3번에 걸쳐서 알고리즘을 바꿨다.

입력한 대로 정답은 제대로 나왔지만 문제는 시간 이었다.

지금부터 내가 풀었던 3개의 알고리즘을 설명해볼 생각이다.

 

1번째 알고리즘

1. 테스트 케이스를 입력 받는다.
2. 총 몇 일 동안 주식을 할 건지 입력할 건지 입력 받는다.
3. 입력된 날들에 대해 반복하면서 각 날의 주식 가격을 입력받는다.
4. max_element 알고리즘을 통해서 vector에서 가장 큰 수의 인덱스를 추출하여 max_idx 변수에 넣어준다.
5. max_idx만큼 반복문을 돌려준다 예를들어, 처음부터 가장 큰 수 까지 total변수를 통해서 값을 계산하여 저장해준다.(Ex. 1 1 3 2 이면 max_idx는 2일 테고, total은 4가 된다.)
6. 계산을 하고 나서 계산한 백터는 필요 없으므로 erase함수를 통해 요소를 지워준다.
7. 이렇게 해서 3번부터 5번까지 반복해서 백터가 비어질 때가지 반복한다.
8. 그리고 최종적으로 total을 출력해주는 알고리즘이다.

 

예시로 [1 1 3 1 2]를 들어보자.

먼저 max_idx는 2이다. 이때, index 0부터 2까지의 합을 total 변수에 저장한다.

이제 index 0부터 2까지는 필요 없으므로 지운다. 그러면 [1 2]가 남는다.

다음 max_idx는 1이다. 이때도, index 0부터 1까지의 합을 total 변수에 더한다.

그리고 index 0부터 1까지 지운다.

백터 v가 빈 상태가 되므로 반복문을 끝내고, total을 출력하며 프로그램을 종료한다.

 

1번째 코드

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int main() {
    cin.tie(NULL);
    cout.tie(NULL);
    ios_base::sync_with_stdio(false);
    int T, day;
    cin >> T;

    long long total = 0;
    for (int i = 0; i < T; i++) {
        cin >> day;
        if (day < 2)
            return 0;
        vector<int> v(day);
        for (int j = 0; j < day; j++) {
            cin >> v[j];
        }

        while (!v.empty()) {
            int max_idx = max_element(v.begin(), v.end()) - v.begin();

            for (int k = 0; k < max_idx; k++) {
                total += v[max_idx] - v[k];
            }

            v.erase(v.begin(), v.begin() + max_idx + 1);
        }
        cout << total<<"\\n";
        total = 0;
    }
   
    return 0;
}

이렇게 코드를 짜니 시간 초과가 뜬다. 처음 생각에는 v.erase(v.begin(), v.begin() + max_idx + 1); 함수가 시간을 많이 먹는다고 생각했다. 그래서 지우는 방법보다 max_idx를 찾는 범위를 조정해서 구하는 방법으로 접근 해보았다.

해봐야 아는 거니깐~~

 

 

2번째 알고리즘

1. 테스트 케이스를 입력 받는다.
2. 총 몇 일 동안 주식을 할 건지 입력할 건지 입력 받는다.
3. 입력된 날들에 대해 반복하면서 각 날의 주식 가격을 입력받는다.
4. 범위를 정해주기 위해 a라는 변수를 선언해 준다.
5. a 부터 max_idx만큼 반복문을 돌려준다.
6. 계산을 하고 나서 계산한 백터는 필요 없으므로 이번에는 erase함수 대신 a변수에 마지막 계산에 사용된 index를 넣어줬다. 여기서 말한 “마지막 계산에 사용된 index”는 당연히 max_idx다.
7. 이렇게 해서 3번부터 5번까지 반복해서 a가 마지막 index를 가르킬 때까지 반복한다.
8. 그리고 최종적으로 total을 출력해주는 알고리즘이다.

 

1번째 알고리즘과 거의 비슷하다.

[1 1 3 1 2] 백터가 있다면, 처음에는 0부터 2까지 계산하고, a에 2+1를 넣어준다.

그러면 다음번에 max_idx를 구할 때 범위는 3 부터 4가 될 것이다.

이런 식으로 구현을 해보았다.

 

2번째 코드

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int main() {
    cin.tie(NULL);
    cout.tie(NULL);
    ios_base::sync_with_stdio(false);
    long long T, day;
    long long a = 0;
    long long max_idx = 0;
    cin >> T;

    long long total = 0;
    for (int i = 0; i < T; i++) {
        cin >> day;
        vector<int> v(day);

        for (int j = 0; j < day; j++) {
            cin >> v[j];
        }
        
        while (a != day) {
            max_idx = max_element(v.begin() + a, v.end()) - v.begin();

            for (int k = a; k < max_idx; k++) {
                total += v[max_idx] - v[k];
            }
            a = max_idx + 1;
        }
        
        cout << total<<"\\n";
        total = 0;
        a = 0;
    }
   
    return 0;
}

근데 시간 초과….ㅎㅎ

반복문을 저렇게 사용하니깐 당연히 시간 초과가 뜨지요

저도 알고 있었는데 88%까지 가서 시간 초과가 뜨길래 기대했는데 아쉽다.

그렇게 해서 그냥 반복문을 없애기 위해서 새로운 알고리즘을 생각해 보았다.

 

 

그렇게 해서 나온 3번째 알고리즘

1. 주어진 테스트 케이스 수(T)를 입력한다.
2. 각 테스트 케이스마다 다음을 수행한다:
   • 날의 수(N)를 입력한다.
   • N일 동안의 주식 가격을 나타내는 배열(vector)을 입력한다.
3. 각 테스트 케이스마다 다음을 수행한다:
   • 초기화된 total 변수를 0으로 설정한다.
   • 배열의 마지막 인덱스에 해당하는 가격을 최댓값(max)으로 설정한다.
   • 배열의 뒤에서부터 두 번째 인덱스부터 시작하여 첫 번째 인덱스까지 탐색한다.
   • 현재 인덱스의 가격이 최댓값보다 작은 경우, 최댓값과 현재 가격의 차이를 total에 더한다. 이는 주식을 사고 팔아 이익을 얻는 과정이다.
   • 현재 가격이 최댓값보다 큰 경우, 최댓값을 현재 가격으로 업데이트한다. 이는 새로운 최댓값을 찾은 경우로, 이후의 날짜에서 이 가격보다 큰 가격을 발견하면 이익을 얻을 수 있다.
4. 각 테스트 케이스마다 계산된 total 값을 출력합니다.

 

3번째 코드

#include <iostream>
#include <vector>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int T;
    cin >> T;

    while (T--) {
        int N;
        cin >> N;

        vector<int> v(N);
        for (int i = 0; i < N; ++i) {
            cin >> v[i];
        }

        long long total = 0;
        int max = v[N - 1]; 

        for (int i = N - 2; i >= 0; --i) {
            if (v[i] < max) {
                total += max - v[i];
            }
            else {  
                max = v[i];
            }
        }
        cout << total << "\\n";
    }

    return 0;
}

이렇게 하면 시간복잡도가 O(N)이 나오게 된다.

 

쉽게 생각하고 시간 복잡도를 먼저 고려 하는 연습을 해야겠음!