https://programmers.co.kr/learn/courses/30/lessons/42584
코딩테스트 연습 - 주식가격
초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때, 가격이 떨어지지 않은 기간은 몇 초인지를 return 하도록 solution 함수를 완성하세요. 제한사항 prices의 각 가격은 1 이상 10,00
programmers.co.kr
문제를 처음 확인할 때 생각해볼 수 있는 가장 쉬운 방법으로는 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
