programming
프로그래머스 주식가격 파이썬 풀이 및 해설
by Kitle · 2020. 08. 06.
프로그래머스 주식가격 퀴즈 풀이 및 해설을 남깁니다.
출처 프로그래머스 : 프로그래머스 주식가격
풀이 깃허브에서 보기 : kitle github
퀴즈 요약 : 리스트로 있는 여러 가격이 매 초마다 있고 가격이 떨어지지 않은 기간이 몇초인지 계산하는 문제
오늘은 특별하게 풀이는 정답 이지만 효율성 테스트에서 실패한 케이스 부터 보시겠습니다.
[솔루션]
퀴즈 자체는 스택/큐로 분류되어 있으나, 아무리 생각해도 Stack/Queue를 활용할만한 포인트가 잘 보이지 않습니다.
그냥 for 문으로 더 빠르게 풀 것 같네요.
모든 원소를 현재 인덱스 부터 마지막 원소까지 모두 탐색한다.(이중 for문 필요)
탐색시마다 카운터를 1증가한다. 탐색중 떨어진 가격과 만나면 break 하여 끝까지 탐색하지 않도록 한다.(효율성) 끝까지 탐색하는 경우는 현재 원소 다음 전체 길이(카운터와 동일)가 곧 정답이다.
모아진 값을 리스트로 붙여 리턴한다.
[효율성 테스트 실패 소스]
def solution(prices):
answer = []
for idx, price in enumerate(prices):
count = 0
for comp in prices[idx+1:]:
count += 1
if comp < price:
break
answer.append(count)
return answer
하지만 효율성 테스트에 실패하고 말았죠. 이보다 더 좋은 방법이 있을까 해서 stack, queue등을 열심히 찾아봤는데, pop(0) 연산으로 스택을 큐처럼 써볼까 했으나 이렇게 하면 시간복잡도가 오히려 떨어진다는 것을 보았네요. 그래서 구글링의 도움을 얻었습니다.
정확하지 않지만 제가 얻은 결론은 enumerate 를 쓰면 성능이 더 안좋을 수 있어, range로 커버 가능하면 range로 처리하는 것이 좋을것 같습니다. 저도 정확하진 않지만 다음과 같이 코드를 수정하니 해결되는 군요. 두번째 for뒤에 슬라이싱을 반복하는 부분이 코드 쓰기엔 편했지만 아마 성능면에서는 좋지 않았었나 봅니다. 이부분은 추후 테스트를 통해 검증해보도록 해야하겠습니다.
그러면 이제 제대로 되는 코드를 보시죠.
[효율성 통과된 케이스]
def solution(prices):
answer = []
for i in range(len(prices)):
ans = 0
for j in range(i+1, len(prices)):
ans += 1
if prices[i] > prices[j]:
break
answer.append(ans)
return answer
위에 코드와 유사하지만 range 부분으로 바뀌었고 슬라이싱 없이 index로 접근해서 성능이 확보된 것으로 보입니다.
슬라이싱은 반복해서 사용하는 경우는 피하고, for문은 최대한 range와 len 을 활용하는 것이 좋을것 같네요.
본 케이스는 좀 더 스터디 해봐야 겠네요.
이상 마치겠습니다.
