프로그래머스 - 주식가격 / Python

문제: https://programmers.co.kr/learn/courses/30/lessons/42584

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

문제 설명

문제 설명

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

제한사항

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

입출력 예

pricesreturn

[1, 2, 3, 2, 3]

[4, 3, 1, 1, 0]

입출력 예 설명

• 1초 시점의 ₩1은 끝까지 가격이 떨어지지 않았습니다.
• 2초 시점의 ₩2은 끝까지 가격이 떨어지지 않았습니다.
• 3초 시점의 ₩3은 1초뒤에 가격이 떨어집니다. 따라서 1초간 가격이 떨어지지 않은 것으로 봅니다.
• 4초 시점의 ₩2은 1초간 가격이 떨어지지 않았습니다.
• 5초 시점의 ₩3은 0초간 가격이 떨어지지 않았습니다.

 

---

정답

def solution(prices):
    # prices 의 길이만큼 answer 배열 생성
    answer = [0] * len(prices)

    # 자신보다 뒤에 있는 값들과 비교하면서, 나보다 작은 값을 만날 때까지 1씩 증가시킴
    for i, price in enumerate(prices):
        for j in range(i + 1, len(prices)):
            if prices[i] > prices[j]:  # 자신보다 작으면 반복 종료
                break
        answer[i] = j - i

    return answer

---

풀이

 이 문제는 가격이 떨어지지 않은 기간을 구하는 문제입니다.  처음에 작성한 코드는 배열에 각각 해당하는 flag를 줘서 flag 참거짓을 통해 연산하도록 했습니다.

 

def solution(prices):
    answer = [i for i in range(len(prices) - 1, -1, -1)]
    flag = [True for _ in prices]

    for i in range(1, len(prices)):
        for j in range(0, i):
            if flag[j] and (prices[i] < prices[j]):
                answer[j] = i - j
                flag[j] = False

    return answer

  수행 결과 정확성 테스트는 모두 통과하지만, 효율성은 모두 실패하는 결과를 볼 수 있습니다. 어떤 부분에서 시간이 오래 걸렸는지 코드를 살펴보니 가격이 한번 떨어져서 연산을 하지 않아도 되는 값을 계속 연산하는 부분이 때문이라고 생각이 되었습니다. 그리고 문제의 알고리즘 분류가 스택/큐 라는 점을 참고하여 flag 대신 큐를 이용해서 다시 도전했습니다.

 

def solution(prices):
    answer = [i for i in range(len(prices) - 1, -1, -1)]
    queue = [0]

    for i in range(1, len(prices)):
        queue.append(i)
        for _ in range(len(queue)-1):
            if len(queue) > 0:
                n = queue.pop(0)
                if prices[i] < prices[n]:
                    answer[n] = i - n
                else:
                    queue.append(n)

    return answer

 각 값들을 차례로 큐에 넣은 다음, 가격이 떨어지면 큐에서 없애고 인덱스 값의 차이를 저장하는 방식을 이용했습니다. 결과는 정확성 테스트는 모두 통과하지만, 효율성 테스트 3,4 는 실패했습니다. 

 스택 또는 큐를 이용하는 방법으로는 이것이 최선이라고 생각하는데 풀리지 않으니 의문이 들어 스택/큐를 이용하지 않고 배열 그대로 계산하는 방식으로 해보았습니다.

def solution(prices):
    # prices 의 길이만큼 answer 배열 생성
    answer = [0] * len(prices)

    # 자신보다 뒤에 있는 값들과 비교하면서, 나보다 작은 값을 만날 때까지 1씩 증가시킴
    for i, price in enumerate(prices):
        for j in range(i + 1, len(prices)):
            if prices[i] > prices[j]:  # 자신보다 작으면 반복 종료
                break
        answer[i] = j - i

    return answer

 해당 값을 기준으로 자신보다 작은 값이 나올때까지 반복하고, 자신보다 작은 값을 발견하면 반복을 종료한 뒤, 인덱스 값의 차이를 저장하는 방식으로 구현하니 효율성 테스트를 통과했습니다.

 결론은 문제의 분류에 사로잡혀 생각을 유연하게 하지 못했던 것이 발목을 잡은 것으로 보입니다.