[C++] 프로그래머스 주식가격

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

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

 

1. 서론

 

만약 이 문제를 아직 풀기 전이거나, 푸는 중인데 모르겠어서 이 글을 봤을 때 당장 이 문제를 버리고 다른 문제를 푸는 것이 당신의 인생을 이롭게 쓰는 법이다. 이 문제는 설명이 너무 부족하다. (지문 자체가 문제를 이상하게 설명함)

 

2. 문제 풀이

 

초 단위로 기록된 주식 가격이 있다. 이 가격이 떨어지지 않은 기간은 몇 초인지 return 하는 문제다.

 

이러한 설명만 읽어보면 참 쉽다. 테스트 케이스도 단 한 개다. 그래서 난 이 문제가 간단한 줄 알았고 보이는 그대로 풀었다.

테스트 케이스는 당연히 맞았고 제출을 했더니 단 한 개만 맞고(내가 아까 맞은 그 케이스) 나머지는 다 틀렸으며 심지어는 효율성은 시간 초과가 났다. 내가 문제를 잘못 이해한 걸까? 이렇게 말고 어떤 방식으로 풀어야 하는데? 이런 생각이 들었다.

 

처음에는 초 단위의 주가를 기준으로 그 뒤의 시간에 그 수 보다 작은 것이 있는지 없는지 체크 했다.

두 번째는 지금 시간 기준 바로 뒤의 값만 보는 것인가 했다. 테스트 케이스는 그렇게 했고, 단 한 개였기 때문에.

둘 다 테스트 케이스는 맞췄지만 제출했을 때는 테케 한 개만 맞고 다 틀렸다.

 

질문하기를 엄청나게 뒤져본 결과 이 문제는 이런 문제였다.

 

초 단위를 기점으로 그 이후에 몇 초 후에 주가가 하락하는 것을 보는 문제이다. 지금 와서 생각해보면 뭔가 문제 설명이랑 정말 같은 말인데 처음 문제를 풀 때는 이게 바로 와 닿지 않는다. (아마도 테스트 케이스 때문에) 

그래서 질문하기에서 봤던 다른 테스트 케이스로 예시를 들겠다.

 

3 4 2 6 5라는 배열이 있다.

 

3을 기준으로 봤을 때 주가가 떨어지는 순간은 2다. 그래서 return 값은 2초 후니까 2다.

2를 기준으로 봤을 때 주가가 떨어지는 순간은 없다. 따라서 return 값은 배열의 끝까지 간 2초 후, 2다.

 

이런 식으로 값을 비교하는 문제이다. 시간 초과 때문에 반복문을 하나만 써야 한다는 생각에 사로 잡혀 또 빙빙 돌았던 것 같다.

 

어떻게든 규칙을 알아내려 애쓰는 모습.... 안쓰럽다

 

3. 코드 설명

 

1) 큐를 쓴 경우

 

#include <queue>
#include <vector>

using namespace std;

vector<int> solution(vector<int> prices) {
    vector<int> answer;
    queue<int> q;
    int i, k;
    
    for (i = 0; i < prices.size(); i++)
        q.push(prices[i]);
    
    k = 0;
    while(q.size() != 1)
    {
        for (i = k; i < prices.size() - 1; i++)
            if (q.front() > prices[i])
                break;
        answer.push_back(i - k);
        q.pop();
        k = prices.size() - q.size();
    }
    answer.push_back(0);
    
    return answer;
}

 

큐를 쓴 이유는 이 문제가 큐 카테고리에 있었기 때문에... 근데 큐를 쓴 게 훨씬 코드가 복잡하다. 큐는 index가 없기 때문에 따로 지칭해줘야 해서....

 

 

2) 큐를 쓰지 않고 푼 경우

 

#include <vector>

using namespace std;

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

 

큐를 안 쓴 편이 훨씬 코드가 간결하다. 마지막 값은 다음 초가 없기 때문에 항상 0이라서 반복문에서도 마지막 항까지 돌리지 않는다.

그리고 반복문을 두 개 돌리면서 각 항마다 비교한다. 주식이 떨어지는 경우가 나타나면 반복문을 빠져나와 answer에 그 길이를 넣는다.

i는 초당 시점 기준, j는 주식이 떨어지는 초 기준이니까 j - i를 하면 그 기간의 초를 알 수 있는 것이다. 

 

하... 진짜 기 빨린다 이런 문제... ㅠ 바로 생각도 안 난다. 논리 자체는 되게 간결한데,,,,, ㅜ