주식가격 - 프로그래머스

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

문제 설명

초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때, 가격이 떨어지지 않은 기간은 몇 초인지를 return 하도록 solution 함수를 완성하세요.

제한사항

• prices의 각 가격은 1 이상 10,000 이하인 자연수입니다.
• prices의 길이는 2 이상 100,000 이하입니다.

---

요약하면 '각 가격이 유지/이익을 보는 기간이 얼마나 되는가?' 뭔가 요약이 안 되는데

내 해결 방법은 이렇다.

1. 가격이 일정하거나 상승하면 임시 목록에 저장해 둔다.
2. 가격이 떨어지면 떨어진 가격과 같아질 때까지 임시 목록에서 꺼내와서 계산한다.
3. 모든 가격 목록에 대해 끝나면, 임시 목록에 있는 모든 데이터에 대해 꺼내와서 계산한다.

이 임시 목록에는 인덱스와 값이 들어간다. 값이 있어야 비교해서 유지된 기간을 알 수 있다.
인덱스도 같이 저장해야, 얼마나 유지되었는지 알 수 있다.
(예를 들어 두번째 가격인데, 7번째 가격이 두번째가격보다 싸다면, 7-2=5, 5초간 유지가 된 것이 된다)

 

위의 해결 방법을 코드로 해결하기 위한 순서는 다음과 같다.

1. 인덱스와 값을 저장한 리스트를 만든다. 이하 '임시 목록'이라 한다. (하나의 리스트를 만들어서 튜플로 넣어도 된다)
2. 모든 가격에 대해 다음을 실행한다.
   
   1. 직전의 가격과 현재 가격을 비교해서, 현재 가격이 더 낮다면 다음을 실행한다
      1. 임시 목록에서 현재 가격보다 큰 가격이 나오지 않을 때까지 뒤에서부터 제거한다.
      2. 제거한 데이터의 인덱스로부터 가격이 유지된 기간을 얻는다.
      3. 유지된 기간을 정답 목록에 넣는다.
   2. 임시 목록에 현재 가격과 현재 인덱스를 넣는다.
3. 임시 목록에 남아있는 모든 데이터에 대해 다음을 실핸한다.
   1. 인덱스로부터 유지된 기간을 구한다.
   2. 유지된 기간은 정답 목록에 넣는다.

 

위의 순서를 코드로 작성하면 다음과 같다

def solution(prices):
	# 1. 인덱스와 값을 저장한 리스트를 만든다
    answer = []
    ascValue = []
    ascIndex = []
    last = 0
    
    # 2. 모든 가격에 대해
    for i in range(len(prices)):
        price = prices[i]
        
        # 2-1. 직전의 가격과 현재 가격을 비교
        if price < last:
			# 2-1-1. 임시 목록에서 현재 가격보다 큰 가격이 나오지 않을 때까지 뒤에서부터 제거한다.
            while last > price:
                value = ascValue.pop()
                index = ascIndex.pop()
                
                # 2-1-2. 제거한 데이터의 인덱스로부터 가격이 유지된 기간을 얻는다.
                # 2-1-3. 유지된 기간을 정답 목록에 넣는다.
                answer[index] = i - index
                
                if len(ascValue) == 0:
                    last = 0
                else:
                    last = ascValue[len(ascValue) - 1]
            
		# 2-2. 임시 목록에 현재 가격과 현재 인덱스를 넣는다.
        ascValue.append(price)
        ascIndex.append(i)
        last = price
        
        answer.append(0)
        
	# 3. 임시 목록에 남아있는 모든 데이터에 대해 다음을 실핸한다.
    pricesLen = len(prices)
    remainAsc = len(ascIndex)
    
    while remainAsc > 0:
        index = ascIndex.pop()
        
        # 3-1. 인덱스로부터 유지된 기간을 구한다.
        # 3-2. 유지된 기간은 정답 목록에 넣는다.
        answer[index] =  pricesLen - 1 - index
        remainAsc = remainAsc - 1
    
    return answer