프로그래머스의 주식가격 문제를 함께 풀어보도록 하겠습니다.
문제
초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때, 가격이 떨어지지 않은 기간은 몇 초인지를 return 하도록 solution 함수를 완성하세요.
- prices의 각 가격은 1 이상 10,000 이하인 자연수입니다.
- prices의 길이는 2 이상 100,000 이하입니다.
예제
입력: [1, 2, 3, 2, 3]
출력: [4, 3, 1, 1, 0]풀이 1
주식 가격이 떨이지지 않는 기간을 구하려면, 현재 가격과 미래 가격을 비교해야겠죠? 우선, 현재 가격보다 미래 가격이 더 비싸다면 가격이 떨어지지 않은 기간에 포함시킬 수 있습니다. 하지만, 미래 가격이 더 싸다면 가격이 떨어지지 않은 기간에 포함시킬 수 없을 것입니다.
예를 들어, 아래와 같은 입력 배열이 주어졌다고 가정해보겠습니다. 100원에 샀던 주식이 500원까지 올랐다가 200원으로 떨어진 경우입니다.
prices=[100, 300, 500, 400, 200]우선 인덱스 0에서는 주식 가격이 100원인데요. 미래의 가격을 보면 이 보다 낮은 가격은 없습니다. 따라서 4초동안 가격이 떨어지는 않았다는 것을 알 수 있습니다.
___
prices=[100, 300, 500, 400, 200]
-----------------> 4초다음 인덱스 1에서는 주식 가격이 300원인데요. 미래의 가격을 보면 계속 이 보다 높다가 인덱스 4에서 가격이 200원으로 300원 아래로 떨어집니다. 문제에서 주어진 예제에 대한 설명을 보시면 이렇게 가격이 떨이진 경우, 그 시점까지 1초를 포합합니다. 그러므로 가격이 떨어지지 않은 기간은 3초가 됩니다.
___ 📉
prices=[100, 300, 500, 400, 200]
------------> 3초다음 인덱스 2에서는 주식 가격이 500원인데요. 미래의 가격을 보면 바로 다음 인덱스에서 가격이 떨어집니다. 따라서 떨어진 시점까지 포함한 1초가 가격이 떨어지지 않은 기간이 되겠습니다.
___ 📉
prices=[100, 300, 500, 400, 200]
--> 1초주식 가격이 400원인 인덱스 3에서도 바로 다음 인덱스에서 가격이 떨어집니다. 따라서 1초동안 가격이 떨어지는 않았다는 것을 알 수 있습니다.
___ 📉
prices=[100, 300, 500, 400, 200]
--> 1초마지막 인덱스에서는 뒤에 미래의 가격이 하나도 없으므로 가격이 떨어지지 않은 기간이 0초로 입력 배열의 길이와 상관없이 항상 동일합니다.
___
prices=[100, 300, 500, 400, 200]
0초위 사고 과정을 살펴보면 우리는 이중 루프를 통해서 이 문제를 해결할 수 있을 것 같습니다.
- 외부 루프에서는 현재 가격을 가리키는 인덱스를 증가시킵니다.
- 내부 루프에서는 미래 가격을 가리키는 인덱스를 증가시킵니다.
- 현재 가격이 미래 가격보다 더 싼 동안 가격이 떨어지지 않은 기간을 1초씩 증가시킵니다.
- 현재 가격보다 비싼 미래 가격을 만나면 내부 루프를 중단하고 다음 현재 가격으로 넘어갑니다.
위 알고리즘으로 파이썬으로 구현해볼까요?
def solution(prices):
result = [0] * len(prices)
for cur in range(len(prices)):
for fut in range(cur + 1, len(prices)):
result[cur] += 1
if prices[cur] > prices[fut]:
break
return result같은 코드를 자바스크립트 구현하면 다음과 같습니다.
function solution(prices) {
let result = new Array(prices.length).fill(0);
for (let cur = 0; cur < prices.length; cur++) {
for (let fut = cur + 1; fut < prices.length; fut++) {
result[cur] += 1;
if (prices[cur] > prices[fut]) {
break;
}
}
}
return result;
}n을 입력 배열의 길이라고 했을 때, 이 알고리즘의 시간 복잡도는 이중 루프로 인해서 O(n^2)이 됩니다.
공간 복잡도는 결과 배열을 차지하는 메모리를 제외하면 O(1)이 되겠습니다.
풀이 2
이전 풀이에서는 현재 가격을 기준으로 미래의 가격이 어떻게 변하는지를 확인했었는데요. 아무래도 같은 미래 가격을 여러 번 접근하다 보니 만족할 만한 성능이 나오지 않는 것 같습니다.
이번에는 발상을 전환하여 미래 대신에 과거의 주식 가격을 확인해보면 어떨까요? 가격이 떨어지는 않는 기간을 구하는 문제이니, 가격이 떨어지는 지점에서 과거의 가격을 살피는 거에요.
우선 가격이 떨어지게 되면, 그 바로 앞 인덱스에서는 가격이 떨어지는 않는 기간이 1초가 됩니다. 그리고 그 앞에 앞 인덱스도 살펴볼 필요가 있는데요. 그 가격이 떨어진 가격보다 더 크다면 그 인덱스에서는 가격이 떨어지는 않는 기간이 2초가 될 것입니다. 이런 식으로 과거를 거슬러 올라가면서 떨어진 가격보다 더 비싼 가격의 인덱스에서 가격이 떨어지는 않는 기간을 구할 수 있습니다.
이러한 상황에서는 스택(Stack) 자료구조를 사용하면 딱인데요. 스택에는 나중에 추가한 원소가 먼저 나오기 때문에, 가까운 과거의 가격을 먼 과거의 가격보다 더 빨리 접근할 수 있기 때문입니다.
이 알고리즘의 기본 아이디어는 스택에 가격이 떨어지지 않은 구간의 가격의 인덱스를 저장해놓는 것입니다. 그러면 스택의 최상단(top)에는 여태까지 최고가의 인덱스가 저장될 것입니다.
입력 배열을 루프 돌다가 가격이 떨어지는 지점에서, 스택에 저장되어 있는 과거 가격 중에서 현재 가격보다 비싼 가격에 대한 인덱스가 있다면, 그 인덱스를 제거하고 가격이 떨어지는 않는 기간을 구할 수 있습니다.
가격이 떨어지는 않는 기간은 현재 인덱스에서 과거 인덱스를 빼주면 됩니다.
result[past_index] = current_index - past_index루프를 다 돌았는데 스택에 남아있는 인덱스는 가격이 떨어진 적이 없다는 뜻입니다. 이 경우에 가격이 떨어지는 않는 기간은 배열에 앞 쪽에 있을수록 커지면 다음 공식으로 구해집니다.
result[i] = len(prices) - i - 1말로만 설명하니 많이 복잡하게 느껴지죠? 우리 이 알고리즘을 위에서 사용했던 예제에 차근차근 적용해보겠습니다.
prices=[100, 300, 500, 400, 200]우선 인덱스 0에서는 주식 가격이 100원이고 아직 과거 가격이 없기 때문에 스택에 현재 인덱스를 추가합니다.
___
prices=[100, 300, 500, 400, 200]
stack=[] + 0 = [0]인덱스 1에서는 주식 가격이 300원이고 스택에 과거 가격의 인덱스가 하나 밖에 없는데 이 인덱스가 있는 가격이 100원입니다. 아직 주식 가격이 상승 중이므로 스택에 현재 인덱스를 추가합니다.
___
prices=[100, 300, 500, 400, 200]
현재가 vs. 과거 최고가 = 300 > 100
stack=[0] + 1 = [0, 1]다음 인덱스 2에서는 주식 가격이 500원이고 스택에 가장 최근에 추가된 인덱스에 있는 가격이 300원입니다. 아직 주식 가격이 상승 중이므로 이 인덱스도 스택에 추가합니다.
___
prices=[100, 300, 500, 400, 200]
현재가 vs. 과거 최고가 = 500 > 300
stack=[0, 1] + 2 = [0, 1, 2]인덱스 3부터는 상황이 좀 달라지는데요. 주식 가격이 400원인데 스택에 가장 최근에 추가된 인덱스에 있는 가격이 500원입니다. 주식 가격이 하락하였으므로 스택에 저장되어 있는 과거 최고가의 인덱스 2를 제거합니다.
___
prices=[100, 300, 500, 400, 200]
현재가 vs. 과거 최고가 = 400 < 500
stack=[0, 1, 2] - 2 = [0, 1]그리고 우리 여기서 막 제거한 인덱스 2에서 위에서 설명드린 공식에 따라서 가격이 떨어지지 않은 기간을 구할 수 있습니다.
result[2] = 3 - 2 = 1다시 스택에 저장되어 있는 과거 최고가를 확인해보면 인덱스 1이 가리키고 있는 300원입니다. 300원이 현재 가격인 400원 보다는 작으므로, 인덱스 1기준으로는 여전히 주식 가격이 상승 중임을 알 수 있습니다. 따라서 현재 인덱스를 스택에 추가합니다.
___
prices=[100, 300, 500, 400, 200]
현재가 vs. 과거 최고가 = 400 > 300
stack=[0, 1] + 3 = [0, 1, 3]인덱스 4에서도 주식이 하락이 이어지고 있습니다. 스택의 최상단에 있는 인덱스의 가격이 400원인데 현재가는 200원이기 때문입니다. 주식 가격이 하락하였으므로 스택에 저장되어 있는 과거 최고가의 인덱스 3를 제거합니다.
___
prices=[100, 300, 500, 400, 200]
현재가 vs. 과거 최고가 = 200 < 400
stack=[0, 1, 3] - 3 = [0, 1]그리고 동일한 방식으로 막 제거한 인덱스 3에서 가격이 떨어지지 않은 기간을 구합니다.
result[3] = 4 - 3 = 1스택을 보면 그 다음 인덱스에 있는 가격이 300원인데요. 여전히 현재가인 200원보다 높네요. 이 인덱스 1에서도 가격이 떨어지지 않은 기간을 구하기 위해서 스택에서 과거 최고가의 인덱스 1를 제거합니다.
___
prices=[100, 300, 500, 400, 200]
현재가 vs. 과거 최고가 = 200 < 300
stack=[0, 1] - 1 = [0]result[1] = 4 - 1 = 3스택에 저장되어 있는 그 다음 과거 최고가는 100원인데요. 현재가보다 작으므로 여기서는 가격이 떨어지지 않은 기간을 구할 수 없습니다. 그래서 현재가를 스택에 추가하겠습니다.
___
prices=[100, 300, 500, 400, 200]
현재가 vs. 과거 최고가 = 200 > 100
stack=[0] + 4 = [0, 4]루프가 끝나고 나면 인덱스 0, 4가 스택에 남아있는 것을 볼 수 있는데요.
여태까지 이 인덱스에 있는 가격보다는 더 내려간 가격은 없었다는 뜻입니다.
따라서 위에서 설명드린 공식에 따라 가격이 떨어지지 않은 기간을 구합니다.
result[0] = 5 - 0 - 1 = 4
result[4] = 5 - 4 - 1 = 0지금까지 설명드린 알고리즘을 파이썬으로 구현해보겠습니다.
아직 구하지 않은 가격이 떨어지지 않은 기간을 표시하기 위해서, 결과 배열의 값을 모두 -1로 초기화하였습니다.
def solution(prices):
result = [-1] * len(prices)
stack = []
for cur in range(len(prices)):
while stack and prices[stack[-1]] > prices[cur]:
pas = stack.pop()
result[pas] = cur - pas
stack.append(cur)
for i in stack:
result[i] = len(prices) - i - 1
return result동일한 코드를 자바스크립트로 구현하면 다음과 같습니다.
function solution(prices) {
const result = new Array(prices.length).fill(-1);
const stack = [];
for (let cur = 0; cur < prices.length; cur++) {
while (stack.length && prices[stack[stack.length - 1]] > prices[cur]) {
const pas = stack.pop();
result[pas] = cur - pas;
}
stack.push(cur);
}
for (let i = 0; i < stack.length; i++) {
result[stack[i]] = prices.length - stack[i] - 1;
}
return result;
}이 풀이의 시간 복잡도는 for 문 안에 while 문 때문에 O(n^2)이라고 생각하기 쉬운데요.
곰곰히 더 생각을 해보면 스택에 인덱스를 추가하거나 제거하는 작업은 입력 배열의 길이와 비례한다는 것을 알 수 있습니다.
만약에 가격이 계속해서 오르기만 한다면, 스택에서 인덱스를 제거할 일은 없고 추가만 n번 하게 될 것입니다.
반대로 가격이 계속해서 떨어지기만 한다면, 스택에서 인덱스를 추가하고 제거하는 작업을 n번 반복하게 되어 총 2n번 하게 될 것이기 때문입니다.
공간 복잡도는 스택이 차지하는 메모리 때문에 O(n)이 되겠습니다.