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

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

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

문제를 처음 확인할 때 생각해볼 수 있는 가장 쉬운 방법으로는 O(n^2) 시간 복잡도를 가지고 있는 완전 탐색이다.

 

그러나 문제를 읽어보면 다음 인덱스 시점의 시간에서 가격이 떨어지느냐 안 떨어지느냐에 따라 return값이 결정된다는 것을 확인할 수 있다.

 

한 가지 주의해야 할 점은 다음 인덱스가 이전 인덱스보다 작다는 것을 알기 전 시간은 이미 1초가 흘렀다고 생각하는 것이고

 

전부 다 돌아보는 것이 아닌 두 번째 for문부터는 바로 앞 인덱스부터 탐색을 시작하면 해결할 수 있다.

 

문제의 분류로는 스택과 큐 카테고리에 존재하지만 오히려 스택과 큐를 활용하여 해결방법을 생각해보더라도 오히려 코드가 더 길어질 것 같으며 큰 차이가 없을 것 같아 다음과 같이 완전 탐색과 같은 방법으로 해결하였다.

 

3 언어의 코드 방식도 전부 동일하며 문제 예시에 대한 이해를 빠르게 한다면 빠른 시간 내에 해결할 수 있을 것 같다.

 

C++

#include <string>
#include <vector>

using namespace std;

vector<int> solution(vector<int> prices) 
{
    vector<int> answer;
    for(int i=0;i<prices.size();i++)
    {
        int cnt=0;
        for(int j=i+1;j<prices.size();j++)
        {
            cnt++;
            if (prices[i] > prices[j])
                break;
        }
        answer.push_back(cnt);
    }
    return answer;
}

Java

class Solution 
{
    public int[] solution(int[] prices) 
    {
        int[] answer = new int[prices.length];
        for(int i=0;i<prices.length;i++)
        {
            for (int j=i + 1;j<prices.length;j++)
            {
                answer[i]++;
                if (prices[i]>prices[j])
                    break;
            }
        }
        return answer;
    }
}

Python3

def solution(prices):
    answer = [0] * len(prices)
    # prices 크기만큼 빈 리스트를 할당.
    for i in range(0,len(prices)):
        for j in range(i + 1, len(prices)):
            answer[i] += 1
            if prices[i]>prices[j]:
                break;
    return answer