# 문제
https://school.programmers.co.kr/learn/courses/30/lessons/42584
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
초 단위로 기록된 주식가격이 담긴 배열 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초간 가격이 떨어지지 않았습니다.
# 풀이 (자바) - 이중 for 문
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] += 1;
if (prices[i] > prices[j]) {
break;
}
}
}
return answer;
}
}
#느낀점
사실 이 문제는 문제 이해가 잘 되지 않아서 지문을 몇 번씩 읽었었다 😂
나와 같은 사람들을 위해 문제에 대해 조금만 더 얘기해보자! 입출력 예시를 '초' 단위 대신 설명을 위해 '일'단위로 바꿔 설명해본다면3,
먼저 총 5일동안의 주식 기간이 있다고 가정해보자!
[1, 2, 3, 2, 3]
- 첫 날 주식의 가격은 1달러이다. 둘째 날, 셋째 날, 셋째 날, 다섯째 날의 주식 가격은 각각 2, 3, 2, 3 달러 이므로 1달러에 산 주식은 4일동안 하락하지 않았다!
- 둘째 날 주식의 가격은 2달러이다. 셋째 날, 넷째 날, 다섯째 날의 주식 가격은 3, 2, 3 달러 이므로 2달러에 산 주식은 3일동안 하락하지 않았다.
- 셋째 날 주식의 가격은 3달러이다. 넷째 날과 다섯째 날의 주식 가격은 총 2달러 3달러이다. 넷째 날에 2달러로, 3달러에 산 주식의 가격보다 낮아, 주식 가격이 하락했다! 주식을 구매한 다음날 하락했으므로, 주식을 구매하고 떨어지기 전까지의 시간인 하루동안 가격이 하락하지 않았다.
- 넷째 날 주식의 가격은 2달러이다. 다섯째 날 주식의 가격은 3달러이다. 2달러에 산 주식은 1일동안 하락하지 않았다.
- 마지막 날(다섯 째 날)의 주식 가격은 하락할 일이 없다. 즉, 0일동안 하락하지 않게 된다.
즉, return 값이 [4, 3, 1, 1, 0]이 되게 되는 것이다.
for (int i = 0; i < prices.length; i++) {
for (int j = i + 1; j < prices.length; j++) {
answer[i] += 1;
if (prices[i] > prices[j]) {
break;
}
}
}
나는 이중 포문을 이용하여 주식 가격이 하락하기 까지의 일 수를 answer[i]에 담는 식으로 풀었다.
차례로 값을 비교한다는 점에서 직관적으로 생각했던 풀이 방법이었는데, 이 문제의 카테고리는 사실 스택/큐 이다. (이중 반복문 사용 시 시간 복잡도도 O(N^2)으로 비효율적이기도 하다...)
그래서 문제를 풀고 난 뒤, 더 효율적인 방법이 있을 거라고 생각해 stack을 사용하여 풀려고 해봤으나 쉽지 않았었다...
2시간을 고민해보다가 해결이 되지 않아, 구글링을 통해 아래 코드를 찾고 이해해보려했다.
# 풀이 (자바) - Stack
class Solution {
public int[] solution(int[] prices) {
int[] answer = new int[prices.length];
Stack<Integer> stack = new Stack();
for (int i = 0; i < prices.length; i++) {
while (!stack.isEmpty() && prices[i] < prices[stack.peek()]) {
answer[stack.peek()] = i - stack.peek(); // answer 인덱스에 얼마만에 찾았는지 적어준다
stack.pop(); // 답을 구했기 때문에 stack에서 제거한다
}
stack.push(i);
}
while (!stack.isEmpty()) { // 값을 구하지 못한 index == 끝까지 가격이 떨어지지 않은 주식
answer[stack.peek()] = prices.length - stack.peek() - 1;
stack.pop();
}
return answer;
}
}
코드 출처: https://girawhale.tistory.com/7
- return할 배열 answer와 주식가격 변화를 시간과 함께 체크할 stack 생성
- 먼저 prices.length만큼 도는 for문으로 prices의 값 하나하나 체크
- 반복문을 돌며 prices[stack.peek]과 비교하여 스택이 비어있거나(=처음), 주식이 감소하지 않았다면 stack에 시간 index를 push
- 만약 감소하는 값이 등장한다면 주식이 감소한 시점이므로 stack에서 해당 인덱스를 제거하고 i(현재 주식의 감소 시점) - stack.peek(주식이 처음 들어간 시점) 값을 answer[stack.peek]값에 넣어준다
- stack에 끝까지 남아 있는 경우는 끝까지 주식 가격이 떨어지지 않는 경우이므로, stack이 비어있을 때까지 prices.length - index - 1를 넣어준다.
코드를 살펴보니, stack이 비어있을 때(처음 시작, i = 0)는 stack,push(0)를 통해 먼저 stack을 생성했다.
그리고 그 다음 반복문을 돌 때(i = 1), prices[1] < prices[stack.peek()]을 while 문 조건으로 사용했다. stack.peek()에는 0, 즉 이전에 push 했던, 이전 인덱스 값이 들어있다!
그리고 주식 가격이 떨어졌을 때, 이전 answer에 총 기간을 넣어주게 된다.
한 풀이 방법에 여러가지 풀이 방법이 있을 수 있다는 것은 코딩의 묘미인 것 같다.
다른 사람들의 더 나은 풀이 방법을 볼 때면, 이런 방법도 있구나! 하면서 무릎을 탁 치게 된다.
나도 언젠간 다른 사람이 무릎을 탁 치는 코드를 짜고싶다 :)
'𝑪𝒐𝒅𝒊𝒏𝒈 𝑻𝒆𝒔𝒕' 카테고리의 다른 글
[Codility] Binary Gap (0) | 2022.10.24 |
---|---|
[프로그래머스] 쿼드압축 후 개수 세기 (0) | 2022.10.22 |
[프로그래머스] 삼각 달팽이 (0) | 2022.10.19 |
[프로그래머스] 두 개 뽑아서 더하기 (0) | 2022.10.19 |
[프로그래머스] 3진법 뒤집기 (0) | 2022.10.16 |