프로그래머스 코딩테스트연습(LV2) - 주식가격

출처 : https://programmers.co.kr/learn/courses/30/lessons/42584

코딩테스트 연습 - 주식가격

문제 설명

초 단위로 기록된 주식가격이 담긴 배열 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초간 가격이 떨어지지 않았습니다.

나의풀이

• 핵심은 for문을 처음부터 2번 돌리지 않는것!! 왜냐하면 효율성이 떨어지기 때문에
• 그래서 '필요할때만 for문을 돌리는 방법'으로 고민을 시작함
• 필요할때 == 지금 가격이 1초전 가격보다 떨어졌을때!

def solution(prices):
    answer = [len(prices)-1]
    for i in range(1, len(prices)):
        answer.append(len(prices)-1-i) // 일단 각 시간마다 가격이 떨어지지 않는 최대 시간을 입력 (첫번째 순회)
        k=1
        while prices[i-k] > prices[i]: // 만약 현재 가격이 1초전 가격보다 하락했을 경우 (2번째 순회)
            if answer[i-k] > k: // 그 전의 가격들과 비교하여 
                answer[i-k] = k // 만약 현재 가격보다 k초전 가격이 비싸다면, 현재 시간과의 차이(k)로 값을 변환
            if k < i:
                k+=1 // k는 i를 초과하지 않는 선에서 1씩 증가
            else:
                break
    return answer