티스토리 뷰
728x90
[Python]프로그래머스 문제풀이 - 주식가격
서문
오늘은 프로그래머스 사이트 / 코딩테스트 / 스택,큐 문제의 첫 시작을 해보겠습니다. 한 번 문제를 살펴보겠습니다.😉
- 프로그래머스 문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/42586
코드의 전개 논리가 궁금하시다면, 밑의 사이트에 들어가서 코드를 작성하여 visualize해주시면 코드가 어떤 식으로 흘러가는지 눈으로 파악하실 수 있습니다!
- 파이썬 튜터 사이트 : http://pythontutor.com/visualize.html#mode=display
1. 문제 설명
초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때, 가격이 떨어지지 않은 기간은 몇 초인지를 return 하도록 solution 함수를 완성하세요.
2. 제한사항
- prices의 각 가격은 1 이상 10,000 이하인 자연수입니다.
- prices의 길이는 2 이상 100,000 이하입니다.
| prices | return |
|---|---|
| [1,2,3,2,3] | [4,3,1,1,0] |
3. 입출력 예 설명
- 1초 시점의 ₩1은 끝까지 가격이 떨어지지 않았습니다.
- 2초 시점의 ₩2은 끝까지 가격이 떨어지지 않았습니다.
- 3초 시점의 ₩3은 1초뒤에 가격이 떨어집니다. 따라서 1초간 가격이 떨어지지 않은 것으로 봅니다.
- 4초 시점의 ₩2은 1초간 가격이 떨어지지 않았습니다.
- 5초 시점의 ₩3은 0초간 가격이 떨어지지 않았습니다.
본문
요약
price라는 배열에 가격이 입력됩니다.
각 자리는 시점입니다.
만약 그 시점의 가격보다 미래의 가격이 낮을 때 그 기간을 answer 배열에 담아서 출력해주면 됩니다.
문제풀이
- 1번 방법
def solution(price):
answer = []
for i in range(len(price)-1):
flag = False
for j in range(i+1,len(price)):
if price[i] > price[j]:
answer.append(j-i)
flag = True
break
if flag == False:
answer.append(len(price)-i-1)
answer.append(0)
return answerDetail Code Review
- 우선 price 길이가 2 < x < 100,000 입니다. 아무래도 이중 for문으로도 문제를 풀 수 있지 않을까 합니다. 더 효율적인 방법이 있다면 안전하게 가는 것이 좋지만, 제 머리는 그렇게 좋지 못합니다... 문제를 보자마자 이중 for문이 생각났기에...
- [1,2,3,2,3] 에서 첫 번째 for문은 1에서 4번 째 2까지 돕니다. 생각해보면 마지막까지 돌 필요가 없기 때문입니다.
- j는 i보다 +1에서 시작하여 price 마지막까지 확인합니다. 즉
i = 1일 때, j는 2,3,2,3까지, i = 2일 때, j = 3,2,3 이런 식입니다.
- flag는 가격이 떨어진 것을 판단하기 위한 변수입니다. 예컨대 가격이 떨어졌다면 true, 아니라면 false를 가집니다.
- price[i]보다 price[j]가 작다면 가격이 떨어진 것으로 가격이 떨어지기 전 기간을 담을 answer에 j-i 값을 넣어줍니다. 예컨대 [1,2,3,2,3]에서 3번 째 3이 다음 2보다 크기때문에 index j = 3, index i = 2를 빼면 1 기간동안 가격이 유지된 것을 알 수 있습니다. 또 flag를 true로 바꿔줍니다.
- 만약 j가 다 확인했는데 가격이 떨어지지 않았다면, j 포문을 나와서 answer에 len(price)-i-1를 넣어줍니다. 이때 -1 을 하는 의미는 인덱스가 0부터 시작하기 때문에 이를 맞춰주기 위함입니다.
- 마지막 포문을 다 돌때까지 마지막 인덱스를 확인하지 않았습니다. 이는 무조건 마지막 인덱스는 기간이 없기에 0을 반환하면 됩니다. 그러므로 answer에 0을 담아줍니다.
- 2번 방법
def solution(price):
answer=[]
for i in range(len(price)):
stack = 0
for j in range(i+1, len(price)):
stack += 1
if price[i] > price[j]:
break
answer.append(stack)
return answer
Detail Code Review
- 컨셉은 i와 j를 확인하면서 가격이 떨어지는 시점까지 stack을 늘려주는 것입니다.
- 만약에 가격이 떨어지는 시점을 발견한다면, 그때까지 쌓인 stack이 가격이 유지된 기간일 것입니다.
- 만약 가격이 떨어진 시점이 없다면 stack은 그 기간을 다 더해서 나옵니다.
- 마지막 구간은 j for문을 타지 않기 때문에 stack = 0으로 위에 있는 풀이와 같이 마지막 값은 무조건 0이 나오게 됩니다.
혹시 문제가 있는 부분이 있으시면 말씀해주세요. 😙
댓글
