문제 내용

문제 설명

초 단위로 기록된 주식가격이 담긴 배열 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초간 가격이 떨어지지 않았습니다.

문제 분석

만약 이번거가 스택 탑보다 작음
	스택 탑이 유지된 초 = 1
	팝
	cnt = 1
	while true
		탑 > 이번거 => 탑 초 = cnt
		cnt++
		아니면 break
아니면 push

작성한 코드

#include <string>
#include <vector>
#include <stack>
#include <iostream>
 
using namespace std;
 
vector<int> solution(vector<int> prices) {
    vector<int> answer(prices.size(), 0);
    stack<int> st;
    st.push(0);
    for(int i = 1; i < prices.size(); i++) {
        if(st.empty()||prices[st.top()]<=prices[i]){
            // cout << "st is empty or top <= prices[i] | top = " << st.top() << " i = " << i << endl;
            st.push(i);
        }
            
        else {
            // cout << "top > prices[i] | top = " << st.top() << " i = " << i << endl;
            answer[st.top()] = 1;
            st.pop();
            int cnt = 2;
            while(!st.empty()) {
                if(prices[st.top()] > prices[i]) {
                    answer[st.top()] = cnt;
                    cnt++;
                    st.pop();
                    continue;
                }
                else break;
            }
            st.push(i);
        }
    }
    
    while(!st.empty()) {
        int i = st.top();
        st.pop();
        answer[i] = prices.size() - 1 - i;
    }
    return answer;
}

이렇게 했더니 실패해서 왜인가 하고 딥시크한테 물어봤음
문제점은 두가지였음

초기 스택 설정
시간 계산 오류

초기 스택에 그냥 냅다 0을 집어넣은 것도 불안정한데 심지어 cnt라는 임의의 변수로 시간 계산을 하다보니까 틀려버림 그래서 수정한 것

#include <string>
#include <vector>
#include <stack>
#include <iostream>
 
using namespace std;
 
vector<int> solution(vector<int> prices) {
    vector<int> answer(prices.size(), 0);
    stack<int> st;
    for(int i = 0; i < prices.size(); i++) {
        if (!st.empty() && prices[st.top()] > prices[i]) {
            // cout << "top > prices[i] | top = " << st.top() << " i = " << i << endl;
            answer[st.top()] = i - st.top();
            st.pop();
            while(!st.empty()) {
                if(prices[st.top()] > prices[i]) {
                    answer[st.top()] = i - st.top();
                    st.pop();
                }
                else break;
            }
        }
        st.push(i);
    }
    
    while(!st.empty()) {
        int i = st.top();
        st.pop();
        answer[i] = prices.size() - 1 - i;
    }
    return answer;
}

우수 코드 분석

// 프로그래머스 책 참고
 
#include <string>
#include <vector>
#include <stack>
 
using namespace std;
 
vector<int> solution(vector<int> prices) {
	vector<int> answer(prices.size());
	stack<int> s;
 
	int priceNum = prices.size();
 
	for(int i = 0; i < priceNum; 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()] = priceNum - s.top() - 1;
		s.pop();
	}
	return answer;
}

초기 설정 맘대로 하지 말고 생각없이 상수쓰지 말자..

개발기록장

탐색기

주식가격