스택/큐 연습문제: 주식가격 (스택을 제대로 활용하는 방법…)
이 문제 하나를 풀기 위해 꼬박 이틀이 걸렸다… 대충 다른 사람들이 푼 문제를 따라서 입력하고 넘어가거나 스킵을 해서 다른문제를 먼저 푼 이후에 다시 돌아와도 됐을텐데 이상한 오기가 생겨서 이 문제 만큼은 반드시 내 힘으로 풀고 넘어가야겠다는 생각이 들었다.
문제 하나를 위해 들인 정신적, 체력적 데미지가 크기는 했지만 고생한 만큼 스택에 대한 이해는 확실히 한 것 같아 자세한 기록을 남겨본다…
문제
초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때, 가격이 떨어지지 않은 기간은 몇 초인지를 return 하도록 solution 함수를 완성하세요.
제한 조건
- prices의 각 가격은 1 이상 10,000 이하인 자연수입니다.
- prices의 길이는 2 이상 100,000 이하입니다.
입출력 예
prices = [1, 2, 3, 2, 3]
return = [4, 3, 1, 1, 0]
- 1초 시점의 ₩1은 끝까지 가격이 떨어지지 않았습니다.
- 2초 시점의 ₩2은 끝까지 가격이 떨어지지 않았습니다.
- 3초 시점의 ₩3은 1초뒤에 가격이 떨어집니다. 따라서 1초간 가격이 떨어지지 않은 것으로 봅니다.
- 4초 시점의 ₩2은 1초간 가격이 떨어지지 않았습니다.
- 5초 시점의 ₩3은 0초간 가격이 떨어지지 않았습니다.
나의 풀이:
def solution(prices):
answer = []
for i in range(len(prices)):
count = 0
for j in prices[i+1:]:
count+=1
if prices[i] <= j:
continue
else:
break
answer.append(count)
return answer
1차 시도. 스택/큐를 정확히 어떻게 사용해야하는지 이 때는 몰랐기 때문에 리스트 안에서 기준 값 i와 그 뒤에 오는 값들 j 를 일일이 비교해가며 가격이 떨어지는 순간까지의 시간을 카운트하여 answer 안에 반환했다.
이 정도면 되겠지하고 제출을 했는데 정확성은 맞았지만 효율성 테스트에서 실행시간이 초과되어 통과하지 못했다.
def solution(prices):
answer = []
for i in range(len(prices)):
if i+1 == len(prices):
answer.append(0)
break
elif prices[i] == min(prices[i+1:]):
answer.append(len(prices) - (i+1))
continue
for j in prices[i+1:]:
if prices[i] > j:
idx = prices.index(j,i+1)
break
idx = len(prices)-1
time = idx-i
answer.append(time)
return answer
2차 시도… for문 사용을 줄이기 위해 if 조건만으로 값을 찾을 수 있는 경우는 최대한 잡아보려했지만 오히려 코드도 복잡해지고 여전히 효율성 테스트를 통과하지 못했다.
def solution(prices):
answer = []
while len(prices) > 0:
try:
idx = prices.index(prices[0]-1)
answer.append(idx)
except:
answer.append(len(prices)-1)
finally:
prices.pop(0)
return answer
3차 시도… 문제가 이렇게 어려울리 없다는 생각에 문제를 다시 읽어본 뒤 주식가격이 1단위로만 증가하고 감소한다는 가정하에 작성한 코드다.
예제로 주어진 prices = [1, 2, 3, 2, 3] 에서 주식가격이 2 이상 증가하거나 감소하지 않았기 때문에 한 번 시도해봤는데 제출한 결과에서는 정확도 테스트를 실패하는 것을 보니 2 이상으로도 증감소가 이루어지는 듯 하다.
def solution(prices):
answer = []
i=1
while len(prices) > 1:
if i == len(prices):
answer.append(i-1)
prices.pop(0)
i=1
elif prices[0] > prices[i]:
answer.append(i)
prices.pop(0)
i=1
continue
else:
i+=1
answer.append(0)
return answer
4차 시도… 나름 스택/큐 공부한 걸 써먹어보겠다고 pop()을 써봤는데 여전히 효율성 테스트에서 실패했다. while문도 한번 밖에 안 썼으니 이번에는 되겠지 했는데 사실 i+=1 을 사용하여 조건을 반복시켜줬기 때문에 for 문을 쓴 것과 마찬가지였나보다.
어떻게든 스스로 풀어보겠다고 해설도 안 보고 몇 시간 동안 정말 희안한 코드들을 다 작성해본 것 같은데 아무리 시도를 해도 효율성 테스트를 통과하지 못했고 머리는 갈수록 과부하 상태에 빠져들었다…
스택 공부
공부했던 내용은 스택 자료구조의 형태와 스택에 push, peek, pop 이 쓰인다는 것 뿐이었지 스택을 어떻게 문제 풀이에 사용하는 지에 대해서는 전혀 공부한 적이 없었다. 그래서 유튜브를 찾아보니 아주 좋은 영상이 있었다.
스택에 대한 기초적인 설명 뿐만 아니라 어떤 형식의 문제에 사용되는지까지 알려주는 것을 보고 조금씩 감이 잡히기 시작했다.
위 영상 외에도 추가적으로 4개 정도의 스택 관련 영상이 더 있었는데 그 중 아래 영상이 지금 풀려고 하는 주식가격 문제와 가장 비슷한 유형인 것 같아 가장 많이 참고를 했다.
영상 설명에 따르면 내가 앞서 작성한 코드들은 모두 순서나 형태만 조금 다를 뿐 모든 값을 하나하나 비교하는 브루트 포스(Brute Force), 즉 완전탐색 알고리즘이다.
브루트 포스로 검색을 할 때는 앞에서부터 순차적으로 값을 비교하게 되는데 이 경우에는 이미 비교를 마친 값은 그 뒤에 오는 값들의 비교를 할 때 도움이 되지 못한다.
그런데 만약 뒤에서부터 역순으로 값을 비교한다면 이미 비교를 마친 값에 대한 정보를 그 다음 값의 비교에 활용할 수 있게 된다. 그리고 그 정보를 활용하기 위한 방법으로 스택을 사용하게 되는 것이다.
그럼 이제 다시 문제를 풀어보자.
스택을 사용한 풀이
prices = [1, 2, 4, 1, 3, 2, 3]
위 리스트가 주어졌을 때, 리스트안의 각 값이 자신보다 더 작은 값을 만나게 될 때까지의 거리를 구해야 한다.
이걸 역순으로 비교해가며 스택을 이용해서 풀면…
-
우선 리스트 맨 뒤쪽은 비교할 값이 없기 때문에 항상 거리가 0이 된다. 거리를 answer에 입력했다면 price 3과 인덱스 6을 스택에 쌓아준다.
-
다음 위치의 값 2를 스택에 쌓여있는 값과 비교해준다. 스택의 3이 2보다 크기 때문에 pop을 해준다. 다음, 더 작은 값을 찾기 위해 그 다음 값을 확인해야하지만 그 다음에는 값이 없으므로 마지막 인덱스인 6과 현위치의 인덱스인 5를 뺀 1을 answer에 넣어준다.
값을 비교했으면 스택에 현위치 5를 넣어준다.
-
그 다음 위치 prices[4]의 값 3과 스택의 2를 비교하면 2가 더 작고, 이후에는 더 작은 값을 찾을 필요가 없으므로 두 값의 인덱스 차, 3 - 2 = 1을 answer로 넣어주면 된다. 다음 price 3과 인덱스 4를 스택에 쌓아준다.
-
이제 1을 비교할 차례다. 스택의 가장 위에서부터 값을 비교하면 1 < 3, 더 작은 값을 찾기 위해 최상단 값을 pop으로 제거하고 계속해서 그 다음 값과 비교를 이어나간다. 다음 값도 1 < 2 이므로 pop을 해주고나면 스택이 비게되므로 (마지막 인덱스 값, 6) - (현 위치의 인덱스, 3) 을 계산하여 3을 answer에 입력해준다. 그리고 마찬가지로 (1, 3)을 스택에 올려준다.
-
앞에서 진행한 작업을 계속해서 이어나가면 된다. 4는 1보다 크므로 answer는 인덱스의 차인 “3 -2 = 1”, pop 없이 바로 다음 스택을 쌓아주면 된다.
-
같은 과정을 반복
-
마지막 1을 비교하면, 현재 스택에 쌓여있는 2와 1중에 더 작은 값이 없으므로 순차적으로 pop을 해주고 결국 스택의 끝에 도달하여 6 - 0 의 값인 6을 answer로 넣어주면 된다. 모든 answer 값을 채웠으므로 마지막 스택은 굳이 추가하지 않아도 된다.
이 과정을 이제 코드로 구현만 하면 된다.
def solution(prices):
answer = [0]*len(prices)
stack = []
for i in reversed(range(len(prices))):
while stack:
if prices[i] > prices[stack[-1]]:
answer[i] = stack[-1] - i
break
else:
stack.pop()
if stack == []:
answer[i] = (len(prices)-1) - i
stack.append(i)
return answer
앞서 설명에서는 시각화를 위해 스택에 prices 값도 같이 넣어줬지만, 실제 계산에는 인덱스 값만 필요하기 때문에 생략해도 문제는 없다.
이렇게 먼 길을 돌고돌아 스택으로 문제를 풀 수 있었다ㅠㅠ 스택을 사용하면 시간복잡도가 O(n)이므로 O(n²)인 브루트 포스 방식보다 효율적인 실행이 가능하다.
다른 사람들의 풀이
def solution(prices):
answer = [0] * len(prices)
for i in range(len(prices)):
for j in range(i+1, len(prices)):
if prices[i] <= prices[j]:
answer[i] += 1
else:
answer[i] += 1
break
return answer
내가 가장 처음 풀었던 방식과 거의 유사하다… 고작 변수 몇개 차이 때문에 이 코드는 간신히 효율성 테스트를 통과했고 나는 통과하지 못했다.
def solution(prices):
answer = [0]*len(prices)
stack = []
for i, price in enumerate(prices):
#stack이 비었이면 false
while stack and price < prices[stack[-1]]:
j = stack.pop()
answer[j] = i - j
stack.append(i)
# for문 다 돌고 Stack에 남아있는 값들 pop
while stack:
j = stack.pop()
answer[j] = len(prices) - 1 - j
return answer
두번째는 prices를 역순이 아닌 앞에서부터 순차적으로 검사하는 방식의 코드다. 마찬가지로 스택을 활용했는데, 정방향으로 알고리즘이 진행되면 이미 비교를 마친 값에 대한 정보를 그 다음 값의 비교에 사용할 수 없게 된다. 그래서 여기에서는 그 부분을 보완하기 위해 정보를 스택에 쌓아두었다가 검사가 모두 끝난 후 남아있는 스택값을 활용해서 answer를 반환하는 것을 볼 수 있다.
댓글남기기