주식가격 문제풀이(C++, 스택/큐)[프로그래머스]

안녕하세요 멍청한 토끼입니다.

이번 문제는 프로그래머스의 스택/큐 Lv2에 해당하는

주식가격 문제 입니다.

포스팅을 시작하겠습니다.

 

※ 저의 풀이가 무조건적인 정답은 아닙니다.

다른 코드가 좀더 효율적이고 좋을 수 있습니다.

다른사람들의 풀이는 언제나 참고만 하시기 바랍니다.

https://programmers.co.kr/learn/courses/30/lessons/42584

코딩테스트 연습 - 주식가격 | 프로그래머스

---

목차

1. 문제 설명

2. 문제 해석

3. 소스 코드

4. 결과

---

3.1 주석 없는 코드

3.2 주석 있는 코드

3.3 테스트 코드

---

1. 문제 설명

초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때, 가격이 떨어지지 않은 기간은 몇 초인지를 return 하도록 solution 함수를 완성하세요.

 

제한사항

prices의 각 가격은 1 이상 10,000 이하인 자연수입니다. prices의 길이는 2 이상 100,000 이하입니다.

예시

prices	return
[1,2,3,2,3]	[4,3,1,1,0]

 

입출력 예시 설명

1초 시점의 ₩1은 끝까지 가격이 떨어지지 않았습니다. 2초 시점의 ₩2은 끝까지 가격이 떨어지지 않았습니다. 3초 시점의 ₩3은 1초뒤에 가격이 떨어집니다. 따라서 1초간 가격이 떨어지지 않은 것으로 봅니다. 4초 시점의 ₩2은 1초간 가격이 떨어지지 않았습니다. 5초 시점의 ₩3은 0초간 가격이 떨어지지 않았습니다.

 

 

---

2. 문제풀이

큐와 스택을 이용해서 문제를 풀어볼까 했는데 팝하고 푸시는하거보다 배열상태로 비교하는게 더 빠르다 생각이 되어서 배열비교로 풀었습니다. 최악의 경우가 댓글로 들어왔습니다. prices가 1~100,000일때 2중 반복문일경우 O(n*n)이므로 약 10,000,000,000(100억)번의 연산이 필요하게되고 시간이 초과하게 됩니다. 코딩테스트시 1억번 연산을 1초로 예상하고 작성하므로 탈락입니다. 질문게시글에 java로 스택을 이용한 풀이를 올려준 김찬정님 코드를 참고했습니다. 풀이는 아래와 같습니다.

 

 

---

3. 소스코드

3.1 주석없는 코드

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

 

3.2 주석있는 코드

 

#include <iostream>
#include <vector>
#include <stack>
using namespace std;
 
vector<int> solution(vector<int> prices) {
    int size = prices.size();
    vector<int> answer(size);
    stack<int> st;
    for (int i = 0; i < size; i++) {
        //스택이 비어있지않고 스택마지막 값이 현재값보다 크다면
        //-> 가격이 떨어졌다면
        while (!st.empty() && prices[st.top()] > prices[i]) {
            //가격이 떨어졌으므로 i - 스택 마지막값 대입
            answer[st.top()] = i - st.top();
            //값제거
            st.pop();
            //반복문인 이유: 가격이 같은값이 유지되었을경우
            //현재값보다 계속작으므로 1개차이씩 넣어주기 위해서다.
        }
        //현재 인덱스를 스택에 넣기
        st.push(i);
    }
    //스택이 빌때까지 반복
    while (!st.empty()) {
        //위에서 특정위치에 이미값을 넣었으므로 pushback이나 insert로하면 안된다.
        //뒤에서부터 넣어야하므로 size-1 에서 top값을 빼준다.
        answer[st.top()] = size - st.top() - 1;
        st.pop();
    }
    return answer;
}

 

 

3.3 테스트 코드 추가

#include <iostream>
#include <vector>
#include <stack>
using namespace std;
 
vector<int> solution(vector<int> prices) {
    int size = prices.size();
    vector<int> answer(size);
    stack<int> st;
    for (int i = 0; i < size; i++) {
        //스택이 비어있지않고 스택마지막 값이 현재값보다 크다면
        //-> 가격이 떨어졌다면
        while (!st.empty() && prices[st.top()] > prices[i]) {
            //가격이 떨어졌으므로 i - 스택 마지막값 대입
            answer[st.top()] = i - st.top();
            //값제거
            st.pop();
            //반복문인 이유: 가격이 같은값이 유지되었을경우
            //현재값보다 계속작으므로 1개차이씩 넣어주기 위해서다.
        }
        //현재 인덱스를 스택에 넣기
        st.push(i);
    }
    //스택이 빌때까지 반복
    while (!st.empty()) {
        //위에서 특정위치에 이미값을 넣었으므로 pushback이나 insert로하면 안된다.
        //뒤에서부터 넣어야하므로 size-1 에서 top값을 빼준다.
        answer[st.top()] = size - st.top() - 1;
        st.pop();
    }
    return answer;
}
 
void print(vector<int> prices, vector<int> answer) {
    vector<int> t = solution(prices);
    if (answer == t)    cout << "정답" << endl;
    else    cout << "틀림" << endl;
}
 
int main() {
    print({ 1,2,3,2,3 }, { 4,3,1,1,0 });
    vector<int> prices, answer;
    for (int i = 1; i <= 100000; i++) {
        prices.push_back(i);
        answer.push_back(100000 - i);
    }
    print(prices, answer);
    return 0;
}

 

4. 결과