https://school.programmers.co.kr/learn/courses/3-/lessons/42584
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
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]
입출력 예 설명
1초 시점의 ₩1은 끝까지 가격이 떨어지지 않았습니다.
2초 시점의 ₩2은 끝까지 가격이 떨어지지 않았습니다.
3초 시점의 ₩3은 1초뒤에 가격이 떨어집니다. 따라서 1초간 가격이 떨어지지 않은 것으로 봅니다.
4초 시점의 ₩2은 1초간 가격이 떨어지지 않았습니다.
5초 시점의 ₩3은 0초간 가격이 떨어지지 않았습니다.
문제 해결 방법
아 이문제는 참 어렵다! 시간 복잡도는 O(N^2)에 맞추면 안되고 O(NlogN)까지 가능하다.
그런데 이 문제 아무리생각해봐도 O(NlogN)로 풀기 어려웠다. 그래서 O(N^2)로 풀어봤는데,,, 끝이 안난다.
이조건 맞추면 저 조건 안맞고, 저 조건 맞추면 이 조건 안맞고 그랬다.
그래서 결국 답을 보고 이해했다.
이 문제는 효율성을 해결하기 위해서는 반드시 스택으로 풀어야한다. 그런데 이 문제 스택을 어디에 적용할지 떠올리기가 참 어렵다.
코드 주석으로 설명하였다.
코드 구현
기존 코드 - 미해결
def solution(prices):
#O(N)으로 구현
answer = []
prices=list(prices)
stackk=[]
newPrices=[]
newPrices = list(prices)
for i in range(len(prices)):
if i == 0:
stackk.append(prices[i])
else:
newPrices.reverse()
if len(newPrices)==0:
break
newPrices.pop()
newPrices.reverse()
cnt=0
#print('prices[i]', prices[i-1], 'newPrices', newPrices)
for price in newPrices:
#print('price', price)
if prices[i-1]<=price:
cnt+=1
answer.append(cnt)
answer.append(0)
#print(answer)
return answer
개선 코드 - 해결
def solution(prices):
answer = []
total = len(prices)
answer = [0] * total
#각 초 시점의 길이를 넣을 배열
stackk = [0]
# 스택을 0으로 초기화 한 이유는 순회를 인덱스 1부터 하기 위해서임
# prices의 0번 인덱스는 스택에 넣고 시작한다.
for i in range(1, total):
# 1부터 total까지 순회한다.
# 0번 인덱스부터 total 인덱스까지 순회할 때, 가격의 증가만 있다면,
# 계속 stackk에 넣는다.
# 만약 가격이 떨어진다면 그때부터는 스택에서 꺼내어서 하락한 가격의 인덱스로부터 길이를 구한다.
while stackk and prices[stackk[-1]]>prices[i]:
a=stackk.pop()
answer[a]=i-a
stackk.append(i)
while stackk: # 스택이 빌 때까지 순회하여 길이를 찾아준다.
#이 스택은 최종적으로 증가한 값들만 남아있다.
a=stackk.pop()
answer[a]=total-a-1
#print(answer)
return answer
시간/공간 복잡도
O(NlogN)
최적화 및 개선
많은 개선을 했다. 음 로직을 아예 뜯어고침
어려웠던 점/느낀점
답지를 안보고 혼자 코드 로직을 생각할 수 있을때 까지 연습하는것 까지 했다.
다음에 또 풀때는 잘 풀었으면 좋겠다.
'코딩테스트 > 문제 풀이 - Python' 카테고리의 다른 글
| [프로그래머스 lv2]기능개발 (0) | 2024.03.11 |
|---|---|
| [프로그래머스 lv1]크레인 인형뽑기 게임 (0) | 2024.02.02 |
| [프로그래머스 lv2]짝지어 제거하기 (1) | 2024.01.31 |
| [프로그래머스 lv2]괄호 회전하기 (1) | 2024.01.31 |
| [프로그래머스 lv2]방문 길이 (1) | 2024.01.30 |