[Programmers] Python 프로그래머스 주식가격 Level 2

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

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

 

분류는 스택/큐로 구분되어있지만 사실 완전 탐색으로도 풀리는 문제다.

 

문제풀이

---

지문 자체가 어렵다는 사람들이 많은 것 같아서 문제를 좀 더 쉽게 설명하겠다.

 

prices의 가격들은 매초 변하는 가격을 뜻하고 가격이 떨어지지 않는 기간은 현재 가격보다 더 낮은 가격이 나온 시간까지 매초(가격의 수) 세면 된다는 뜻이다.

 

그래서 예시에서 \1은 그 뒤에 \1보다 낮은 시간이 없기 때문에 4초(4개의 가격) 동안 가격이 떨어지지 않는 것이고 마지막 \3은 그 뒤에 남아있는 시간이 없기 때문에 0초가 된 것이다.

 

단지 지문에서 "가격이 떨어지지 않은 기간은 몇 초인지"라고만 있었기에 이를 헷갈려서 질문에 올린 사람들이 많은 것 같다.

 

어려운 문제가 아니므로 바로 전체 코드로 넘어가겠다.

 

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

 

3번째 줄은 prices의 전체 범위를 탐색하겠다는 것을 뜻하고 5번째 줄은 현재 가격보다 떨어지는 시간이 나올 때까지 남은 시간을 반복하여 세는 반복문이다.

 

만약 현재 가격보다 낮은 시간이 있다면 그 뒤에 가격은 고려할 필요가 없기에 break를 통해 바로 반복문을 탈출하면 된다.

 

그렇게 카운트한 값을 answer에 추가하면 된다.

 

결과 화면

 

다만 의문인 점은 prices의 길이는 100,000(10만) 이하이고 완전 탐색은 O(n^2)의 시간 복잡도가 걸리므로 1초당 5천만~1억 정도 연산이 가능한 Python을 기준으로 최악의 테스트 케이스가 나온다면 시간 초과가 걸릴 수밖에 없다.

 

하지만 Input이 작은 정확성까진 이해가 됐으나 상당히 큰 Input이 들어오는 효율성까지 통과된 거로 봐서는 최악의 경우까진 Input이 들어오지 않게 설정한 것 같다.