문제 설명
초 단위로 기록된 주식가격이 담긴 배열 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초간 가격이 떨어지지 않았습니다.
※ 공지 - 2019년 2월 28일 지문이 리뉴얼되었습니다.
나의 풀이
class Solution {
public int[] solution(int[] prices) {
int[] answer = new int[prices.length];
int min = 10001;
for(int price : prices) {
if(price < min) {
min = price;
}
}
for(int i = 0; i < prices.length; i++) {
int price = prices[i];
if(price == min) {
answer[i] = prices.length - 1 - i;
continue;
}
int cnt = 0;
for(int j = i + 1; j < prices.length; j++) {
cnt++;
if(prices[j] < price) {
break;
}
}
answer[i] = cnt;
}
return answer;
}
}
Java
복사
Remark
•
스택/큐 분류였는데 마땅히 방법이 떠오르지 않아 배열로 풀이함
◦
시간복잡도가 이라 효율성 테스트를 대비해 최솟값 조건을 넣었는데, 길어진 코드 양 대비 큰 속도 차이는 없었음(약 10ms 단축). 간략화하면 아래와 같음
class Solution {
public int[] solution(int[] prices) {
int[] answer = new int[prices.length];
for(int i = 0; i < prices.length; i++) {
for(int j = i + 1; j < prices.length; j++) {
answer[i]++;
if(prices[j] < prices[i]) {
break;
}
}
}
return answer;
}
}
Java
복사
•
스택을 이용한 다른 분들의 풀이 분석
◦
이해하는데 한참 걸렸는데, 아래 그림처럼 이해하면 꽤 직관적으로 받아들일 수 있음
import java.util.Stack;
class Solution {
public int[] solution(int[] prices) {
Stack<Integer> beginIdxs = new Stack<>();
int i=0;
int[] terms = new int[prices.length];
beginIdxs.push(i);
for (i=1; i<prices.length; i++) {
// 현재 가격(prices[i])보다 높았던 것들은 상승+보합 기간이 기록되면서 스택에서 사라짐(그림 상 1, 2 과정)
// 이 과정에서 주식 그래프상 하락 구간이 완전히 소멸된다고 이해하면 직관적임
while (!beginIdxs.empty() && prices[i] < prices[beginIdxs.peek()]) {
int beginIdx = beginIdxs.pop();
terms[beginIdx] = i - beginIdx;
}
// 하락장이 나타날 때까지 스택에 계속 쌓임
beginIdxs.push(i);
}
// 이 구간에는 완전한 상승만 그리는 주식 그래프를 처리함(그림 상 3 과정)
// 마지막 날까지 하락이 없었던 것들은 인덱스를 통해 기록됨
while (!beginIdxs.empty()) {
int beginIdx = beginIdxs.pop();
terms[beginIdx] = i - beginIdx - 1;
}
return terms;
}
}
Java
복사
