[백준] 11501번 주식

문제: 11501번: 주식

basic-algo-lecture/workbook/0x11.md at master · encrypted-def/basic-algo-lecture

basic-algo-lecture/workbook/0x11.md at master · encrypted-def/basic-algo-lecture

 

• 내 풀이

 

#include <bits/stdc++.h>

using namespace std;

struct sorted {
    bool operator()(pair<int, int> a, pair<int, int> b) {
        // 우선 순위 큐는 기본적으로 최대힙으로 동작하기 때문에 비교 연산자의 의미가 일반적인 less<>와 반대로 적용된다.

        // 만약 가격이 같으면 인덱스 오름차순으로 정렬
        if (a.first == b.first)
            return a.second > b.second; // 그냥 벡터같은거였으면 a.second < b.second 인데 우선순위큐는 최대힙이므로 이를 반대로 해줘야함..

        // 가격이 다르면 가격 내림차순으로 정렬
        return a.first < b.first;
    }
};

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

    int t;
    cin >> t;
    while (t-- > 0) {
        int n;
        cin >> n;

        // first 요소로 내림차순 정렬
        // first 는 가격, second 는 인덱스
        priority_queue<pair<int, int>, vector<pair<int, int>>, sorted> stocks;
        vector<int> stockPrices(n); // 주식 가격만 저장하기
        for (int i = 0; i < n; i++) {
            int price;
            cin >> price;
            stocks.push({ price, i });

            stockPrices[i] = price;
        }
        int curIdx = 0;
        int curCnt = 0;
        long long profit = 0;

        pair<int, int> maxStock = stocks.top();
        stocks.pop();

        while (!stocks.empty()) {
            if (curIdx < maxStock.second) {
                // 만약 현재 인덱스가 maxStock 의 인덱스보다 작으면 주식 구매~
                profit -= stockPrices[curIdx];
                curCnt++;
                curIdx++;
                continue;
            }

            if (curIdx == maxStock.second) {
                // 현재 인덱스가 maxStock 인덱스랑 같으면 주식 판매~
                profit += maxStock.first * curCnt;
                curCnt = 0;
                curIdx++;
            }
            // 현재 인덱스가 maxStock 인덱스보다 크거나 같을 때 새로운 maxStock 꺼내
            maxStock = stocks.top();
            stocks.pop();
        }
        cout << profit << "\n";
    }

    return 0;
}

 

 

흠.. 나는 우선 순위 큐 이용해서 풀었는데 다른 사람 풀이 보니까 우선 순위 큐 안 쓰고도 풀 수 있었다.

• 효율적인 풀이

#include <iostream>
#include <vector>

using namespace std;

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

    int t;
    cin >> t;
    while (t-- > 0) {
        int n;
        cin >> n;

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

        long long profit = 0;
        int maxPrice = 0;

        // 오른쪽에서 왼쪽으로 탐색
        for (int i = n - 1; i >= 0; i--) {
            if (stockPrices[i] > maxPrice) {
                maxPrice = stockPrices[i]; // 최대값 갱신
            } else {
                profit += (maxPrice - stockPrices[i]); // 최대값보다 작으면 차익 계산
            }
        }

        cout << profit << "\n";
    }

    return 0;
}

 

 

 

참고자료:

https://chatgpt.com/share/67bc14ec-4400-800b-aa62-a474f8f3d712

ChatGPT - 비효율적 코드 최적화

내가 짠 코드보다 훨씬 효율적인 코드를 짜줬다;; 이 방법을 계속 기억하고 있는게 좋을 것 같다. 우선 순위 큐를 너무 남발하면 안 될 것 같다;;