Gidhub BE Developer

[Programmers] 주식 가격

2018-09-25
goodGid
Algorithm

Problem

Problem URL : 주식 가격

[1] Answer Code (18. 09. 25)

#include <string>
#include <vector>
#include <stack>
#include <iostream>
#define p pair<int,int>
using namespace std;

vector<int> solution(vector<int> prices) {
    vector<int> answer;
    stack<p> s;
    
    int size = (int)prices.size();
    int chk[100005] = {0,};
    
    s.push({prices[0],0});
    for(int i=1; i<size; i++){
        while(! s.empty() && s.top().first > prices[i]){
            int value = s.top().first;
            int idx = s.top().second;
            s.pop();
            chk[idx] = i - idx;
        }
        s.push(  {prices[i],i}  );
    }
    
    while(! s.empty()){
        int value = s.top().first;
        int idx = s.top().second;
        s.pop();
        chk[idx] = (size-1) - idx;
    }
    
    for(int i=0; i<size; i++){
        cout << chk[i] << " ";
        answer.push_back(chk[i]);
    }
    return answer;
}

Review

  • 다음과 같은 코드도 맞는 코드이다.

  • 하지만 중복되는 코드가 있었기 때문에 줄였다.

for(int i=1; i<size; i++){
    if(s.top().first < prices[i]){
        s.push(  {prices[i],i}  );
    }
    else{
        while(! s.empty() && s.top().first > prices[i]){
            int value = s.top().first;
            int idx = s.top().second;
            s.pop();
            chk[idx] = i - idx;
        }
        s.push(  {prices[i],i}  );
    }
}

[2] Wrong Code (18. 09. 25)

#include <string>
#include <vector>
#include <stack>
#include <iostream>
#define p pair<int,int>
using namespace std;

vector<int> solution(vector<int> prices) {
    vector<int> answer;
    stack<p> s;
    
    int size = (int)prices.size();
    int chk[100005] = {0,};
    
    s.push({prices[0],0});
    for(int i=1; i<size; i++){
        if(s.top().first < prices[i]){
            s.push(  {prices[i],i}  );
        }
        else{
            while(! s.empty()){ // [1]
                int value = s.top().first;
                int idx = s.top().second;
                s.pop();
                chk[idx] = i - idx;
            }
            s.push(  {prices[i],i}  );
        }
    }
    
    
    while(! s.empty()){
        int value = s.top().first;
        int idx = s.top().second;
        s.pop();
        chk[idx] = (size-1) - idx;
    }
    
    for(int i=0; i<size; i++){
        cout << chk[i] << " ";
        answer.push_back(chk[i]);
    }
    return answer;
}

Review

  • 틀린 이유를 한동안 찾았다.

  • 그 이유는 [1]처럼 했을 때 같은 값이 들어오게 되면 문제가 발생했다.

입력으로
[1, 1, 3, 3, 1, 2, 5]이 들어온다면

[1] 처럼 했을 시
[1 2 1 1 2 1 0 ]와 같은 답이 나온다.

하지만
while(! s.empty() && s.top().first > prices[i]) 로 바꾼다면
[6 5 2 1 2 1 0 ]와 같은 답이 나온다.

즉 같은 값이 연속으로 들어온다면 지속이 되야한다.

Recommend

Index