Algorithm[프로그래머스][스택/큐]주식 가격

문제점 1

문제를 제대로 이해하지 못했다.

 

• 문제 설명

문제에서 주어진 테스트케이스만 이용하여 알고리즘을 짰다. -> 테케 1번 빼고 전부 실패했다.

테스크 케이스 2개를 더 만들어서 알고리즘을 생각했다.

#1 [1, 2, 3, 2, 3, 1]

#2 [5, 8, 6, 2, 4, 1]

#2에서 4초의 2가 나오면 3초의 6만 체크를 하지 않았다. 하지만 1초의 5, 2초의 8입장에서도 주식의 가격이 하락했으므로 가격이 떨어지지 않은 기간으로 체크해주면 안된다. 

 

문제점 2 

위의 내용을 수정하여 작성했더니 정확도는 다 맞았으나 효율성이 0점이 나왔다. ->이중for문을 사용하여 O(n^2) 였으나 실패하였다.

 

이중for문을 수정하여 효율성 테스트 성공

-> 앞에서 뒤로 체크하였으나, 뒤에서 앞으로 체크

 

def solution(prices):
    answer = [0]*len(prices)
    for i in range(len(prices)):
        for j in range(i+1, len(prices)):
            if prices[i] <= prices[j]:
                answer[i]+=1
            else:
                answer[i]+=1
                break
    return answer

 

 

추가 ++

이중포문을 수정하여 정답은 맞았으나, 문제의 요구사항인 스택/큐를 이용하지 않았다.

스택을 이용하여 알고리즘을 해결하니 효율성이 훨씬 좋아진걸 확인할 수 있었다. 

def solution(prices):
    answer = [len(prices) - i - 1 for i in range(len(prices))] #각 시점의 기간으로 초기화
    stack = [] #주식 가격을 체크할 스택
    for i in range(len(prices)): #i는 현재시점이다. 현재 시점에서 stack에 있는 이전의 주식 가격을 체크한다.
        while stack: #체크할 주식 가격이 있는 경우만 while문을 돈다.
            idx = stack[-1] # idx는 현재시점의 가격와 비교될 주식의 값이다.
            if prices[idx] > prices[i]: #주식의 가격이 떨어졌으면
                answer[idx] = i-idx #해당 주식이 오른 기간은 현재시점 - 그때 시점이다.
                stack.pop() #떨어진 주식은 더이상 체크할 필요가 없어서 pop
            else:
                break
        stack.append(i) #확인한 현재 주식의 값은 과거의 확인될 값이 된다.
    return answer