프로그래머스 스택/큐 주식가격 c++ 풀이

그냥 이중포문으로 돌리면 될 것 같아서 코드를 짰다.

vector<int> solution(vector<int> prices)
{
    vector<int> answer;
    for (int i = 0; i < prices.size(); i++)
    {
        int count = 0;
        for (int j = i + 1; j < prices.size() | prices[i] <= prices[j]; j++)
        {
            count++;
        }
        cou
        answer.push_back(count);
    }
    return answer;
}

이렇게 풀었는데

문제 조건을 잘못이해했나 보다. 코테에서 이러면 안될텐데...

 틀린부분 고쳐서 제출

vector<int> solution(vector<int> prices)
{
    vector<int> answer;
    
    for (int i = 0; i < prices.size(); i++)
    {
        int count = 0;
        for (int j = i + 1; j < prices.size(); ++j)
        {
            count++;
            if (prices[i] > prices[j])
                break;
        }
        answer.push_back(count);
    }
    
    return answer;
}

 이중포문 써서 효율성 떨어질 줄 알았는데 통과함... 기준이 너그러운가

 

 

개선 아이디어

나름 카테고리가 스택/큐이니 그렇게 풀어보자 싶었다.

시간 복잡도 줄일 때 가장 먼저 해야할 건 중복되는 연산이 있는지 살펴보는 것 인 것 같다.

직관적으로 가장 눈에 띄는건 항상 앞의 놈의 숫자가 더 크다는 것이었다. 뭔가 앞에 연산을 누적해서 사용할 수 있을 것 같음.

그리고 뭔가 스택일 것 같은 느낌이 왔음.

3

2

3

2

1

이런 식으로 스택에 넣어두고, 위에 것 부터 꺼내면서 계산 할 수 있을까? 

할 수 있을 것 같음...

스택으로 계산했을 때 이전 결과 값은 현재 주식 가격 하나 이후에 대한 결과를 알려줌. 뭔가 누적해서 사용할 수 있을 것.

그럼 상황은 두개로 나뉜다.

1. 현재 주식 가격 <= 직후 주식 가격 (주식이 오르거나 유지된 것)
   
   직후 주식 가격의 결괏 값은 이전에 계산했을 것이다. 
   이 값을 n이라고 할 때, n은 직후 주식 가격이 상승하거나 유지된 시간이다.
   현재부터 직후에 주식 가격이 올랐으므로, 그 시간은 1초가 늘어난 n+1초가 될 것.
   
   
   
2. 현재 주식 가격 > 직후 주식 가격 (주식이 떨어진 것)
   
   안타깝게 주식 가격이 떨어졌다.
   이 경우 직후 주식 가격의 결괏값에 상관없이 1이다.

위 로직대로 코드를 짜봄.

vector<int> solution(vector<int> prices)
{
    vector<int> answer;
    stack<int> answer_stack;
    for (int i = prices.size() - 1; i >= 0; i--)
    {
        if (answer_stack.empty())
            answer_stack.push(0);
        else
        {
            if (prices[i] <= prices[i + 1])
                answer_stack.push(answer_stack.top() + 1);
            else
                answer_stack.push(1);
        }
        cout << answer_stack.top() << endl;
    }
    return answer;
}

ㅋㅋ 근데 안됨

로직이 잘못됐음ㅜㅜㅋㅋ 시간 낭비^^

생각해보니 그냥 하나하나 비교해야할 것 같다.

다른 사람 코드나 보자 (허무...)

 

 

다른 사람 코드 분석

vector<int> solution(vector<int> prices) {
    vector<int> answer(prices.size());
    stack<int> s;
    int size = prices.size();
    for(int i=0;i<size;i++){
        while(!s.empty()&&prices[s.top()]>prices[i]){
            answer[s.top()] = i-s.top();
            s.pop();
        }
        s.push(i);
    }
    while(!s.empty()){
        answer[s.top()] = size-s.top()-1;
        s.pop();
    }
    return answer;
}

스택으로 푼 사람의 코드이다.

처음에 보고 이해하는 것도 힘들었음 자괴감,,,

쉽게 말해 s는 전체 기간을 통틀어 가격이 한 번도 떨어지지 않은 주식 가격의 인덱스를 저장하는 스택이다.

이 로직은 이전에 for문 안의 현재 주식 가격(prices[time])보다 높은게 있으면 주식이 한 번이라도 해당 가격(prices[s.top()]보다 떨어진 적이 있다는 뜻이므로, 주식이 떨어지지 않은 시간인 그 간격(time - s.top())을 answer에 저장한다. 

원래 코드를 보기가 힘들어서 변수 명을 좀 바꾸고 주석도 달았다.

 

vector<int> solution(vector<int> prices)
{
    vector<int> answer(prices.size());
    stack<int> s;

    // 전체 시간을 돌면서
    for (int time = 0; time < prices.size(); time++)
    {
        // 이전 주식 가격들을 현재 가격과 비교해 주식 가격이 떨어진 애들을 조사한다.
        while (!s.empty() && prices[s.top()] > prices[time])
        {
            // 가격이 떨어지지 않은 기간을 기록하고
            answer[s.top()] = time - s.top();
            // s에서 빼버린다.
            s.pop();
        }
        s.push(time);
    }

    // 이제 s에 남은 애들은 가격이 한 번도 떨어지지 않은 애들이다.
    while (!s.empty())
    {
        // 이 경우 가격이 떨어지지 않은 기간은 전체 기간에서 해당 가격이 발생한 시각을 뺀 것이다.
        answer[s.top()] = prices.size() - s.top() - 1;
        s.pop();
    }

    return answer;
}

좋은 로직인 것 같다.

시간이 얼마나 절약될지는 모르겠지만, 어쨌든 이것도 이중 포문이고 모든 애들과 비교해야 하므로 아주 빠를 것 같지는 않다.

내 코드와 비교해서 개선된 점은, 한 번 주식 가격이 떨어진 걸로 판단된 애들은 재조사하지 않는다는 점이다.

내 코드보다 얼마나 효율성이 좋을지 궁금해서 돌려봤다.

음...? 좀 더 빠르긴 한데, 거의 차이가 없다.

이해하려고 한참 들여다 봤는데 허무하군

 

문제 푸는 것보다 다른 사람 코드 보는게 더 오래 걸렸음.

그래도 이런 생각 어떻게 하지? 천재다 싶은 코드라서 재밌었다.