티스토리에 처음 쓰는 PS 문제가 될 친구입니다!
저번 학기에 자료구조 수업을 들었기 때문에 수업에서 듣지 못했던 해시보다는 스택/큐가 훨씬 익숙할 것이라고 생각해서 이 문제를 첫 업로드 소재로 삼았는데.. 글쎄 쉽지가 않네요 ㅋㅋㅋㅋ
목차
0. 문제 설명
초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때, 가격이 떨어지지 않은 기간은 몇 초인지를 return 하도록 solution 함수를 완성하세요.
0.0. 제한사항
- prices의 각 가격은 1 이상 10,000 이하인 자연수입니다.
- prices의 길이는 2 이상 100,000 이하입니다.
0.1. 입출력 예
| prices | return |
| [1, 2, 3, 2, 3] | [4, 3, 1, 1, 0] |
0.2. 입출력 예 설명
- 1초 시점의 ₩1은 끝까지 가격이 떨어지지 않았습니다.
- 2초 시점의 ₩2은 끝까지 가격이 떨어지지 않았습니다.
- 3초 시점의 ₩3은 1초뒤에 가격이 떨어집니다. 따라서 1초간 가격이 떨어지지 않은 것으로 봅니다.
- 4초 시점의 ₩2은 1초간 가격이 떨어지지 않았습니다.
- 5초 시점의 ₩3은 0초간 가격이 떨어지지 않았습니다.
1. 풀이 과정
생각보다 문제를 이해하는 데에도 꽤 오랜 시간이 걸렸습니다.
다음 턴이 존재한다면 return값은 최소 1이 되야 한다는 것도 문제를 몇 번 읽고 나서야 알았습니다 ㅋㅋㅋㅋ
그래서 가장 처음에 생각한 것은 이중 for문을 써서 첫 for문에서는 price를 하나씩 가져오고, 두 번째 for문에서는 이후 시간들을 다 탐색해서 자신보다 작아지는 순간을 찾아서 answer에 push_back 해주는 방식을 생각했습니다.
이 방식은 O(N^2)이 걸리기도 하고, 스택과 큐를 사용하지 않은 방법이기 때문에 문제에서 원하는 풀이는 아닐 것이라고 생각은 했지만 stack이나 queue를 사용하는 더 효율적인 방식은 생각나지 않아서 먼저 이중 for문으로 정답을 제출했습니다. 예상 외로 정확성과 효율성을 모두 만족해서 통과했습니다.
하지만 분명 stack/queue로 문제를 푼 사람이 있을 것이라 생각했고 역시나 이미 stack으로 풀어내신 분이 있었습니다.
스택에 index를 담고, 그 index를 바탕으로 answer에 값을 넣는 방식이었습니다.
아래 사진을 보시면 아시겠지만 저는 처음에 코드를 제대로 이해하지 못해서 예시로 여러 숫자들을 넣어보고 나서야 이해하고 코드를 다시 짤 수 있었습니다.
먼저 stack 하나를 만듭니다. (s)
i가 0부터 prices의 size 미만까지 증가한다고 놓고 (i는 시간이 됩니다)
만약 stack이 비어있다면 i를 stack에 넣고
stack에 하나라도 값이 존재한다면 prices[s.top()]와 prices[i]을 비교해서
prices[i]보다 prices[s.top()]가 더 작은 경우 answer[s.top()]에 i-s.top()을 넣어줍니다. 이 뜻은 i라는 시간에서 s.top()이라는 시간을 빼 준다는 의미가 됩니다.
그리고 s.pop()를 통해 s.top를 s에서 빼줍니다.
이 작업을 prices[s.top()]이 prices[i]보다 큰 경우 계속해서 반복해줍니다. (당연히 s가 비면 멈춥니다.)
그리고 작업이 끝나면 i를 s에 넣어줍니다.
prices[i]가 prices[s.top()]보다 큰 경우 i를 s에 넣습니다.
이 작업을 반복해서 i가 size에 도달하면 s에 남아있는 값(index)들은 주식의 마지막 가격보다 최소 같거나 더 낮은 가격일 것입니다. 이 친구들은 가격이 내려가지 않았기 때문에 answer[s.top()]에 prices.size()-s.top()-1으로 저장을 하면 되겠죠.
(이 부분에서 잘 이해가 되지 않으신다면, 4초의 주식가격이 10초까지 내려가지 않았다고 한다면 가격이 떨어지지 않은 시간은 11 - 4 - 1인 6초가 되겠죠. 인덱스가 0부터 시작하기 때문에 -1를 추가로 빼 주는 것입니다.)
2. 소스 코드
2.0. 이중 for문으로 해결한 첫 답안
#include <string>
#include <vector>
using namespace std;
vector<int> solution(vector<int> prices) {
vector<int> answer;
for (int idx = 0; idx < prices.size(); ++idx){ // 하나씩 가져와서
int chk = 0;
for(int i = idx+1; i < prices.size(); ++i){
chk++;
if(prices[idx] > prices[i]) // 비교한다
break;
}
answer.push_back(chk); // answer에 넣는다
}
return answer;
}
2.1. stack을 사용한 답안
#include <string>
#include <vector>
#include <stack>
using namespace std;
vector<int> solution(vector<int> prices) {
vector<int> answer(prices.size());
stack<int> s;
int size = prices.size(); // 계속 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 - 1 - s.top(); // 종료 시간 - 당시 시간
s.pop();
}
return answer;
}
3. 후기
신기하게도 이중 for문과 stack간의 효율성에는 차이가 거의 없었습니다.
for 안에 while이 들어가면서 이중 for문과 비슷하게 비교작업을 하면서 생긴 딜레이라고 추정됩니다.
결론은 이중 for문이 PS에서 그렇게 나쁜 것만은 아니었다(?)고 할 수 있겠습니다.
출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges
최근댓글