[4코1파] 4명의 안드로이드 개발자와 1명의 파이썬 개발자의 코딩 테스트 서막 : 4코1파
Rule :
하루에 1문제씩 풀기.
한 문제당 30분씩은 고민하기.
왜 그렇게 풀었는지 공유하기.
하루라도 놓친다면 벌금은 1,000원
START :
[3코1파] 2023.01.04~ (49일차)
[4코1파] 2023.01.13~ (40일차)
Today :
2023.02.21 [49일차]
프로그래머스 LV2
주식가격
https://school.programmers.co.kr/learn/courses/30/lessons/42584
문제 설명
초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때, 가격이 떨어지지 않은 기간은 몇 초인지를 return 하도록 solution 함수를 완성하세요.
제한사항
prices의 각 가격은 1 이상 10,000 이하인 자연수입니다.
prices의 길이는 2 이상 100,000 이하입니다.
입출력 예
입출력 예 설명
1초 시점의 ₩1은 끝까지 가격이 떨어지지 않았습니다.
2초 시점의 ₩2은 끝까지 가격이 떨어지지 않았습니다.
3초 시점의 ₩3은 1초뒤에 가격이 떨어집니다. 따라서 1초간 가격이 떨어지지 않은 것으로 봅니다.
4초 시점의 ₩2은 1초간 가격이 떨어지지 않았습니다.
5초 시점의 ₩3은 0초간 가격이 떨어지지 않았습니다.
※ 공지 - 2019년 2월 28일 지문이 리뉴얼되었습니다.
문제 풀이 방법
문제 옆에 붙어있던게 스택/큐 라서 스택 or 큐를 활용하면 되는구나.. 얻어먹은 문제
사이즈 보니까 앞부분부터 체킹하고, 뒤에 부분도 같이 봐줘야 하는거라 queue로 구현했고
차근차근 주식가격을 앞부터 popleft() 한후에,
남은 큐에 있는걸 하나씩 체크해서 price 보다 s가 높으면 break 해서 값을 구하는 식으로 풀었다.
갑자기 효율성 테스트 나와서 깜짝놀랐고
버르장머리없이 튀어나옴
3,4,5 에서 자꾸 ... 거리면서 시간끌어서 나랑 밀당함
효율성밀당남...
아무래도 더 효율성 있게 풀 수 있는 해답이 있나보지?
(어쩔티비)
증빙
내 코드
from collections import deque
def solution(prices):
answer = []
queue = deque(prices)
while queue:
price = queue.popleft()
s = 0
for q in queue:
s+=1
if price > q:
break
answer.append(s)
return answer다른 사람 풀이
- answer의 값을 주식의 가격이 떨어지지 않았을 경우로 초기화
- prices를 순회하며 stack의 top의 인덱스보다 현재 price의 값이 작을 경우,
pop후, answer값을 수정하는 것을 반복 - 모든 prices의 값이 떨어지지 않았다는 가정하에 answer의 값을 초기화한다.
prices = [1, 2, 3, 2, 3, 1]일 경우 answer = [5, 4, 3, 2, 1, 0]
=> answer을 max값으로 초기화 : answer = [ i for i in range (length - 1, -1, -1)]
-
prices를 순회할 때 증가하는 경우에는 answer의 값을 변경할 필요가 없으나,
감소하는 경우가 있다면 그 때 이전의 stack에 저장된 인덱스들을 비교 해,
감소하는 경우라면 해당 answer의 값을 (작아질 때의 인덱스 - stack의 인덱스) 를 구해서
감소하기 전의 시간을 구해 answer의 값을 업데이트이집 코드 잘하네 좋네
여담
빨리 끝났네 오늘 숙오이~
