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

▶문제설명

코딩테스트 연습 > 스택/큐 > 주식가격

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

▶ 설계

---

prices의 길이가 2 이상 100,000이하이고,

prices에 저장된 각 가격은 1 이상 10,000이하의 자연수이다.

2중 for문으로 일일이 확인하도록 구현하는 방법이 가장 먼저 떠올랐다.

이렇게 나이브한 알고리즘으로 문제를 해결한다고 하면

100,000개의 가격 각각에 대해 1초에 가격이 1부터 1씩 증가한다고 했을 때 최대 10,000번을 확인하게 된다.

1부터 10,000까지 1씩 증가시키고 그 다음 또 1부터 10,000까지 1씩 증가시키는 것을 반복했다고 한다면

따라서, 최악의 경우에 대략적으로 100,000 * 10,000 = 1,000,000,000이 된다고 생각했다.

10억이라는 수는 매우 큰 숫자이므로 시간 제한이 1초라면 TLE가 발생하게 될 것이다.

30분간 시간 복잡도를 줄일 방법을 고민해봤으나 마땅한 방법이 떠오르지 않는다.

일단 위에서 말한 방법대로 한번 구현해보자.

▶ 구현

---

2중 for문으로 각각의 가격에서 몇초가 지났을 때 원래의 가격보다 작아지는지 확인해보자.

vector<int> solution(vector<int> prices) {
    vector<int> answer;
    int end = prices.size();
    
    for(int begin=0; begin<end; begin++){
        int cntBigger = 0;
        for(int now = begin+1; now<end; now++){
 
        }
        answer.push_back(cntBigger);
    }
 
    return answer;
}

3번째 라인에서 end변수에 prices의 사이즈를 담았다.

그러면 end-1이 마지막 인덱스가 된다.

7번째 라인에서 begin+1부터 end-1까지 순회하면서 문제에서 요구하는대로 cntBigger의 값을 만들어주고 answer에 cntBigger 값을 push_back 하도록 구현했다.

이제 7번째 라인의 for문 내부에서 어떤 연산을 해줘야 하는 걸까?

vector<int> solution(vector<int> prices) {
    vector<int> answer;
    int end = prices.size();
    
    for(int begin=0; begin<end; begin++){
        int cntBigger = 0;
        for(int now = begin+1; now<end; now++){
            if(prices[begin] <= prices[now]){
                cntBigger++;
            }
            else{
                cntBigger++;
                break;
            }
        }
        answer.push_back(cntBigger);
    }
    
    return answer;
}
 

5~11번째 라인에서 begin+1부터 end-1까지 순회하면서 begin이 가리키는 가격보다 now가 가리키는 가격이 크거나 같은 경우를 카운팅하다가 작아지는 순간에 멈춘 뒤 answer에 push_back 하도록 구현했다.

은근히 까다로운 부분은  begin이 가리키는 가격보다 now가 가리키는 값이 작을 경우였다.

만약 입력이 [1, 3, 2, 1]로 주어지면 출력은 [3, 0, 0, 0]이 아니라 [3, 1, 1, 0]이 되어야 한다.

1초만에 값이 바뀌면 0이 아니라 1이 되어야하는 것이다.

cntBigger 값은 증가시키되  begin이 가리키는 가격보다 now가 가리키는 값이 작을때는 break문으로 for문을 빠져나오도록 구현하여 해결했다.

begin이 마지막 값을 가리킬 때는 begin+1이 end와 같아지므로 내부의 for문의 조건식을 만족하지 못해 0이 push_back 된다.

▶ 결과

---

TLE를 예상했는데 결과는 만점이었다.

시간 복잡도 계산을 잘못한건지 채점 데이터가 빈약한 건지 잘 모르겠다.

(시간 복잡도 계산에 실수가 있다면 댓글로 알려주시면 감사하겠습니다 !)

▶Solution

---

[소스코드 보기]