[BOJ 11501, C++, Python 3] 주식

https://www.acmicpc.net/problem/11501

11501번: 주식

 

 

풀이

풀이가 O(N+N)과 O(N) 2가지가 존재합니다. 하지만 파이썬은 O(N)만 통과합니다.

 

C++ 풀이 O(N+N)

문제를 보자마자 대부분의 사람들이 왼쪽에서 오른쪽으로 확인하는 방법을 찾아볼 것 입니다.

그래서 → 방향으로 확인하는 방법은 주가의 값(arr[i])을 받고, pair(arr[i], i)로 묶어서 정렬하는 방법입니다.

이 정렬하는 벡터를 max_val이라고 하고, 인덱스를 거꾸로 n-1부터 확인해주면 max_val[i],first가 arr 값중에서 최댓값될 것이고, arr[i]값이 같을 때 max_val[i].second는 i의 값을 최댓값 순서대로 보여줄 것 입니다.

 

그러면 for문을 돌려서 max_val[j].second와 i를 비교한 후에 i가 second보다 작으면 답에 차이값을 더해주고, 아니라면 while문을 이용하여 아직 확인하지 않은 배열중에서 최댓값을 찾아주면 됩니다.  이때 아직 확인하지 않은 배열에서 값을 뽑아내야하니 visit 배열이 필요하겠네요.

 

코드

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
 
const int N = 1e6 + 1;
int t, n, visit[N];
vector<int> arr;
vector<pair<int, int>> max_val;
 
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    
    cin >> t;
    while (t--) {
        cin >> n;
        
        arr.resize(n);
        max_val.resize(n);
        memset(visit, 0, sizeof(visit));
 
        for (int i = 0; i < n; i++) {
            cin >> arr[i];
            max_val[i] = make_pair(arr[i], i);
        }
 
        sort(max_val.begin(), max_val.end());
        
        long long ans = 0;
        int j = n - 1;
 
        for (int i = 0; i < n; i++) {
            visit[i] = 1;
            if (max_val[j].second != i) ans += max_val[j].first - arr[i];
            else {
                while (j >= 0 && visit[max_val[j].second]) j--;
            }
        }
 
        cout << ans << "\n";
    }
 
    return 0;
}

 

 

Python 3 풀이 O(N)

이번엔 관점을 달리하여 ←방향으로 풀어봅시다. 이때는 그냥 val = arr[-1]이라고 잡고, val >= arr[i]면 답에 차이값만큼 더해주고, val < arr[i]이면 val = arr[i]로 업데이트해주면서 for문을 돌리면 됩니다. 그러면 항상 val이 최대값임이 보장이 되니까 O(N+N) 풀이보다 더 간단하게 풀 수 있습니다.

 

코드

fast input을 사용하지 않으면 시간 초과가 나옵니다.

input = __import__('sys').stdin.readline
 
for _ in range(int(input())):
    n = int(input())
    arr = [*map(int, input().split())]
 
    ans = 0
    val = arr[-1]
    for i in range(n-1, -1, -1):
        if arr[i] <= val: ans += val - arr[i]
        else: val = arr[i]
    print(ans)