https://programmers.co.kr/learn/courses/30/lessons/42584
코딩테스트 연습 - 주식가격
초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때, 가격이 떨어지지 않은 기간은 몇 초인지를 return 하도록 solution 함수를 완성하세요. 제한사항 prices의 각 가격은 1 이상 10,00
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] |
| [2, 4, 4, 3, 4] | [4, 2, 1, 1, 0] |
입출력 예 설명
1초 시점의 ₩1은 끝까지 가격이 떨어지지 않았습니다.
2초 시점의 ₩2은 끝까지 가격이 떨어지지 않았습니다.
3초 시점의 ₩3은 1초 뒤에 가격이 떨어집니다. 따라서 1초간 가격이 떨어지지 않은 것으로 봅니다.
4초 시점의 ₩2은 1초간 가격이 떨어지지 않았습니다.
5초 시점의 ₩3은 0초간 가격이 떨어지지 않았습니다.
문제 풀이
주가 정보를 나타내는 prices를 역순으로 순회합니다. 순회하면서 현재 주식 가격과 주식 가격이 상승장으로 유지되는 시간을 스택에 저장합니다. 주식 가격이 떨어지지 않고 유지되는 시간은 스택에 있는 주가 정보(현재 시점 이후의 주식 정보)와의 비교를 통해서 구할 수 있습니다.
스택 와 관련 자료 구조를 초기화합니다.
마지막 시점의 주식 가격은 문제 정의상 유지되는 시간이 0입니다. 이 정보를 주가 유지 시간을 나타내는 times 리스트에 추가하고 스택에 반영합니다.
1 단계: 4 번째 시점의 주식 (2)
현재 주식 가격은 2입니다. 현재 시점 이후의 주식 정보를 스택에서 살펴보면 주가가 3이고 유지 시간이 0인 것을 알 수 있습니다. 현재 주가 2보다 다음 주가 3이 높으므로 현재 시점 이후로 주식 가격 2 이상으로 유지됩니다.
그렇다면 현재 시점부터 얼마나 오랫동안 해당 주가가 유지될까요? 현재 시점에서 주가가 떨어지지 않고 유지되는 시간을 구하는 데 결정적인 도움을 주는 것은 다음 주가가 떨어지지 않고 유지되는 시간입니다. 다음 주가(3)가 떨어지지 않고 유지되는 시간은 곧 해당 시간 동안에는 주식 가격은 적어도 기준 주가(3) 보다 크거나 같다는 말입니다. 따라서 현재 시점의 주가(2)는 다음 시점의 주가(3)까지 떨어지지 않으며, 이후 다음 시점의 주가(3)가 유지되는 시간까지도 떨어지지 않는 것을 보장할 수 있습니다. (다음 시점의 주가까지 유지되는 시간 1 + 다음 시점의 주가가 유지되는 시간 0)
현재 주가 2가 유지되는 시간을 구했다면 이제 다음 주가에 대한 정보는 필요 없습니다.
n 번째 주가를 기준으로 (n - k) 번째 주가가 n 번째 주가보다 큰 경우를 생각해봅시다. (n - k) 번째 주가는 최종적으로 n 번째 주가에서 하락장을 형성합니다. 즉 (n + l) 번째 주가는 (n - k) 번째 주가의 유지 시간을 구하는 데 영향력을 미치지 않습니다.
반대로 n 번째 주가를 기준으로 (n - k) 번째 주가가 n 번째 주가보다 작거나 같은 경우를 생각해봅시다. 앞선 연산에서 n 번째 주가의 유지시간을 구할 때 (n + l) 번째 주가가 떨어지지 않는 시간을 더해서 구하였습니다. 따라서 n 번째 주가의 유지시간에는 (n + l) 번째 주가의 유지시간 정보가 들어있으며 (n - k) 번째 주가는 n 번째 주가 유지 시간만 고려하면 됩니다.
스택에 비어있으므로 더 이상 비교할 다음 시점의 주가 정보가 없습니다. 따라서 현재 시점의 주식은 주가 2를 1만큼 유지합니다. 이러한 정보를 이전 시점의 주식과의 비교를 위해 스택에 저장합니다.
2 단계: 3 번째 시점의 주식 (3)
현재 주식을 다음 주식과 비교합니다. 다음 주식의 가격이 더 작으므로 현재 주가는 다음 시점에 떨어지는 것을 의미합니다.
다음 시점에 떨어지므로 주식의 주가 유지 시간은 1입니다. 이를 스택에 저장합니다.
3 단계: 2 번째 시점의 주식 (2)
현재 시점의 주가 2는 다음 시점의 주가 3과 그다음 시점의 주가 2보다 모두 크거나 같습니다. 즉 현재 시점의 주가 2는 다다음 시점의 주가 2가 유지되는 시간까지 떨어지지 않는 것이 보장됩니다. 이를 반영하여서 현재 시점의 주식 가격이 유지되는 시간을 구합니다.
최종 주가 유지 시간을 스택과 times 리스트에 저장합니다.
4 단계: 1 번째 시점의 주식 (1)
현재 시점의 주가 1은 다음 시점의 주가 2보다 작으므로 다음 시점의 주가가 유지되는 시간만큼 주가가 떨어지지 않는 것이 보장됩니다.
현재 시점의 주가에 대한 정보를 스택과 리스트에 갱신합니다.
최종적으로 주가의 유지 시간 정보가 담긴 리스트를 반환합니다.
소스 코드
메인 솔루션 함수
def solution(prices):
stack = [(prices[-1], 0)]
times = [0]
# prices 를 역순으로 순회하기 위한 인덱스
idx = len(prices) - 2
time = 1
while idx >= 0:
price = prices[idx]
# 주가 유지 시간이 결정된 경우
if (not stack) or (stack and price > stack[-1][0]):
# 정보 저장
stack.append((price, time))
times.append(time)
# 다음 주식 정보를 가리키고 보유 시간을 1로 초기화
idx -= 1
time = 1
# 현재 시점을 기준으로 다음 시점까지의 주가가 떨어지지 않았으므로 주가 유지 시간을 더한다
else:
_, t = stack.pop(-1)
time += t
# 유지 시간의 역순을 출력
return times[::-1]
if __name__ == '__main__':
assert solution([1, 2, 3, 2, 3]) == [4, 3, 1, 1, 0]
assert solution([1, 4, 4, 3, 4]) == [4, 2, 1, 1, 0]
dhsong95/-PRACTICE-Programmers-Algorithm
Contribute to dhsong95/-PRACTICE-Programmers-Algorithm development by creating an account on GitHub.
github.com
'알고리즘 풀이 > 프로그래머스' 카테고리의 다른 글
| 알고리즈 풀이: [프로그래머스] 전화번호 목록 (0) | 2020.06.02 |
|---|---|
| 알고리즘 풀이: [프로그래머스] 완주하지 못한 선수 (0) | 2020.06.01 |
| 알고리즘 풀이: [프로그래머스] 쇠막대기 (0) | 2020.05.29 |
| 알고리즘 풀이: [프로그래머스] 프린터 (0) | 2020.05.28 |
| 알고리즘 풀이: [프로그래머스] 기능개발 (0) | 2020.05.27 |
