[프로그래머스/Level2] 주식 가격

문제 설명

초 단위로 기록된 주식가격이 담긴 배열 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일 지문이 리뉴얼되었습니다.

---

나의 풀이

[Python(파이썬)]

def solution(prices):
    answer = [n for n in range(len(prices)-1, -1, -1)]
    stack = [0]
    for i in range(1, len(prices)):
        while stack and prices[i] < prices[stack[-1]]:
            temp = stack.pop()
            answer[temp] = i - temp
        stack.append(i)
    return answer

 

 

학습한 내용

※ 문제를 풀기 전 체크 할 내용

- prices의 각 가격은 1 이상 10,000 이하인 자연수 -> ₩1은 떨어질 일이 없다. 

 

풀이 과정
1. answer = [0 for _ in range(len(prices))]로 구현
2. answer = [n for n in range(len(prices)-1, -1, -1)]로 구현

 

1.  answer = [0 for _ in range(len(prices))]로 구현 -> 좋은 방법 X

-> answer을 가격이 한 번도 떨어지지 않았을 경우로 초기화

 

처음 풀이 할때는

1) 가격이 떨어지지 않을 때 리스트 값을 어떻게 전부 1씩 올릴 것 인가? 

2) 가격이 한번 떨어지고 나면 스택에서 값을 뺄텐데 그럼 인덱스 정리를 어떻게해서 나머지 1을 올릴 것인가?

이렇게 구현을 하고 있었다. 

 

1. answer, temp에 prices의 길이만큼 0으로 초기화
ex) len(prices) = 5, answer = [0,0,0,0,0], temp = [0,0,0,0,0]
2. prices를 for문으로 돌면서 가격이 떨어지지 않으면 stack에 append
3. 가격이 떨어지면 stack에서 pop

위와 같이 생각을 했으나 

그러면 stack에 값이 하나 들어올때마다 for문을 계속 돌면서 temp 리스트의 전체 값에 1더해야 하고 가격이 떨어질 땐 stack의 인덱스 값이 자꾸 변동하여 순서 저장하는데도 시간과 공간이 필요했다. 

그래서 저런 방법들을 해결하기 위해서 검색해봤더니 이중 for문을 사용해서 풀이한 방법, stack을 이용한 방법, queue를 이용한 방법 등 정말 다양한 방법들이 나왔다.

 

 

2. answer = [n for n in range(len(prices)-1, -1, -1)]로 구현

-> answer을 가격이 한 번도 떨어지지 않았을 경우로 초기화

 

처음에 값이 한 번도 떨어지지 않았을 경우로 answer을 초기해둔다면 값이 떨어질 때만 해당 리스트 값을 바꾸면 되는 것이다. 

 

    # 가격이 내리지 않은 경우로 초기화
    answer = [n for n in range(len(prices)-1, -1, -1)]
    # stack에는 index로 저장
    stack = [0]
    for i in range(1, len(prices)):
        # 스택이 값이 있고 prices[i]이 prices[stack[-1]]보다 작으면 while 실행 
        while stack and prices[i] < prices[stack[-1]]:
            temp = stack.pop()
            answer[temp] = i - temp
        stack.append(i)

 

 

 

 

---

문제 출처

코딩테스트 연습 - 주식가격