프로그래머스 level2 주식 가격

1. 문제 파악하기

- prices의 각 가격은 1~10,000 이하인 자연수 & prices의 길이는 2이상 100,000 이하 → level 1에서보단 prices의 길이가 조금 긴편이지만 그래도 적당한 길이.

 

2. 문제 접근하기

- 초 단위로 기록된 주식 가격이 담긴 배열 prices가 매개변수로 주어지고, 가격이 떨어지지 않은 기간은 몇초인지 retrurn해야함. → 1초의 가격이 2이고 2초 가격이 1이면 return 배열에 들어가는 1초 가격이 떨어지지 않은 기간은 1초이다. 1초 가격이 2, 2초가격이 3, 3초 가격이 1이면 return 배열에 들어가는 1초 가격이 떨어지지 않은 기간은 2초이다.

 

3. 주의할 점

level 1 과 다르게 인자로 주어지는 값의 길이가 많이 커졌습니다. 이때 단순하게 level 1에서 생각한 방법으로 코드를 작성하시다간 시간초과가 일어날 가능성이 높습니다. 이번 문제에선 커트라인을 꽤 크게 주어진 듯하지만 개인적으로도 만족하지 않은 코드입니다. 다른 사람들 풀이의 댓글에보면 스택을 이용하면 O(n)로 문제를 풀 수 있다고 합니다. 저도 지금 당장은 생각이 나지도 않고 다른 사람들 풀이에도 O(n^2)으로 푼 방법 밖에 없어서 한번 생각해봐야겠습니다. ㅎㅎ

 

4. 정답 코드 및 해석

제가 문제를 푼 방법은 다음과 같습니다.

def solution(prices):
    answer = [0 for i in range(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

시간 복잡도를 신경쓰지 않는다면 생각보다 간단하게 문제를 해결할 수 있습니다.

저는 우선 answer이라는 배열에 prices길이만큼 0이라는 숫자들을 담았습니다.

그런 다음 다들 보이시겠지만 2중 for문을 사용하여 O(n^2)으로 문제를 해결했습니다.

이 코드는 원소 하나씩 차례대로 비교하면서 값을 구하는 방법이죠.

이렇게 코드를 작성하면 아래와 같이 케이스를 해결할 수 있습니다.

테스트 케이스 결과

 

5. 마치며

오늘은 level 2의 문제를 보았지만 그 중에서도 가장 짧고 간단한 코드들을 보았습니다. level 2라고해서 level 1과 크게 다를 것은 없습니다. 다만 코드의 길이가 조금 늘어나고 level 2부터는 시간 복잡도를 생각하면서 문제를 해결하기 시작해야합니다. 이번 문제에서는 O(n^2)로도 문제가 해결됐지만 일반적으로 대기업 코딩테스트에서는 조금 힘들 가능성이 높겠죠. 문제를 해결했다고 해서 만족하고 넘어가는 것이 아니라, 조금 더 나은 코드들을 생각해보시고 그 방법으로 다시 문제를 풀어보시는 것이 좋겠습니다.