강의로 돌아가기
Sparkling-SAKE

O(n^2)으로 푼 것 같은데 효율성이 모두 불합격입니다ㅜ

풀이방향이 그냥 잘못된 걸까요?

작성중인 코드―solution.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <string>
#include <vector>
#include <stack>
#include <unordered_map>
#include <algorithm>
#include <iostream>

using namespace std;

using INDEX = int;
using VALUE = int;

vector<int> solution(vector<int> prices) {
    vector<int> answer(prices.size(), 0);
    vector<bool> isClear(prices.size(), true);
    int idx = 0;
    stack<pair<INDEX, VALUE>> s;

    while (idx < prices.size())
    {
        if (s.empty())
        {
            s.push(make_pair(idx, prices[idx]));
            isClear[idx] = false;
            idx++;
        }

        for (int i = 0; i < isClear.size(); ++i)
        {
            if (!isClear[i])
                answer[i]++;
        }

        while (!s.empty() && s.top().second > prices[idx])
        {
            auto temp = s.top();
            s.pop();
            isClear[temp.first] = true;
        }

        s.push(make_pair(idx, prices[idx]));
        isClear[idx] = false;
        idx++;
    }

    return answer;
}
1 개의 답변
hiwg08

주식 가격이 떨어진 시점에서의 원소는 앞으로의 취급 대상이 아니기 때문에, 현재 적어주신 while문을 통해 바로 pop을 하고 더 이상 push를 하지 않습니다. (예시 : [4, 1, 6, 8, 5] --> 4에서 1로 주가 하락, 6, 8에서 5로 주가 하락으로 인해 최종적으로 나오는 스택은 [1, 5] / [5, 6, 7, 8, 2] --> 5, 6, 7, 8에서 2로 주가 하락으로 인해 최종적으로 나오는 스택은 [2]) 효율성에서 틀리신 이유로는 아마 isClear 배열에 대한 루프 추가로 인한 것 같은데, 앞에서 말씀드렸다시피 while문에서 pop으로 빠진 원소는 더 이상의 고려 대상이 아니기 때문에 isClear 배열로 pop한 원소를 한번 더 확인할 필요가 전혀 없습니다. 즉, while문에서 pop하면서 주가가 유지되는 시간을 그 즉시 넣어줘도 41~43의 과정에 전혀 영향을 주지 않는다는 뜻입니다. isClear 배열을 뺀 후, 34~38, 41~43 줄에서 시간을 바로 넣어주는 방식으로 개선하면 됩니다.

답변 쓰기
이 입력폼은 마크다운 문법을 지원합니다. 마크다운 가이드 를 참고하세요.