알고리즘
100일 동안 매일 알고리즘을 하면? - 11일차
유병각
2022. 1. 10. 15:00
https://programmers.co.kr/learn/courses/30/lessons/42584
코딩테스트 연습 - 주식가격
초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때, 가격이 떨어지지 않은 기간은 몇 초인지를 return 하도록 solution 함수를 완성하세요. 제한사항 prices의 각 가격은 1 이상 10,00
programmers.co.kr
수학으로 풀었다.
약간 수학적 귀납법, DP 느낌으로 푼것같은데 이게 직관적인 풀이는 아닌것같긴하다. 다른 사람들의 코드를 보니깐 다 고만고만한데, 다들 시간복잡도 O(N^2) 으로 풀었다. 내 코드 또한 O(N^2) 이긴한데 break 문 덕분에 시간초과가 안난듯하다.
def solution(prices):
ret = [0] * len(prices);
for i in range(len(prices) - 1):
if prices[i] <= prices[i + 1]:
continue;
elif prices[i] > prices[i + 1]:
ret[i] = 1;
if (i > 1):
for j in range(i - 1, -1, -1):
if prices[j] > prices[i + 1]:
if ret[j] == 0:
ret[j] = (i + 1 - j);
continue;
else:
break;
for i,v in enumerate(ret):
if v == 0:
ret[i] = len(ret) - 1 - i;
return ret