[프로그래머스 코딩테스트 고득점 Kit] - 스택/큐

[프로그래머스 코딩테스트 고득점 Kit] - 스택/큐

아래 코드들은 Case에 맞게 straightforward한 설명을 위해, 별도의 리팩토링을 하지 않은 코드입니다.

기능개발 - level 2

문제

작업의 개수progresses, speeds 의 크기 <= 100 인 것을 감안하였을 때, 특별한 알고리즘을 요구하지 않는 문제인 것 같다. 문제의 제시 조건대로 정확하게 구현하는 것으로 문제 해결을 할 수 있다.

필자가 생각한 로직은 다음과 같다.

1. $ 0 \leq i \leq n-1 $ 까지의 작업들을 순차적으로 진행하였을 때, 각 작업들이 배포되는데 걸리는 시간을 계산
   1. $i$번째 작업이 배포되는데 걸리는 시간 : 남은 진도 $\lceil(100-progresses[i]) / speeds[i] \rceil $
2. $ 0 \leq i \leq n-1 $ 까지의 작업들을 배포할 때, 한번의 배포에서 배포되는 작업의 수 계산.
   1. Erase 작업이 Front에서 빈번하게 발생하므로, Queue를 사용하는 것이 효율적이라고 생각
3. Queue에 모든 작업들을 순서대로 넣은 다음, 남은 작업들을 하나씩 꺼내면서 이후의 작업 중 배포 시간이 더 빠른 작업들을 모두 pop 한 다음, 카운트 증가

#include <string>
#include <vector>
#include <cmath>
#include <queue>
using namespace std;

vector<int> solution(vector<int> progresses, vector<int> speeds) {
    vector<int> answer;
    int size = progresses.size();
    vector<int> times(size);
    for(int i=0; i<size; i++){
        times[i] = ceil((100.0 - progresses[i]) / speeds[i]);
    }
    queue<int> Q;
    for(int i=0; i<size; i++){
        Q.push(times[i]);
    }

    while(!Q.empty()){
        int t = Q.front(); Q.pop();
        int cnt = 1;
        while(!Q.empty() && Q.front() <= t){
            Q.pop();
            cnt++;
        }
        answer.push_back(cnt);
    }
    return answer;
}

프린터 - level 2

문제

문제에서 제시한 수행 과정을 충실히 Simulation하면 되는 쉬운 문제다.

필자는 추가적으로 Max-heap을 이용하여, 남은 대기열에서 가장 우선 순위가 높은 작업의 우선순위를 $O(logN)$

시간에 구할 수 있도록 만들어주었다.

이 후는 문제에서 기술한 것과 같이, 특정 작업을 꺼내되 현재 작업 보다 Max-heap에서 가장 우선순위가 높은 작업이 존재할 경우 다시 큐에 넣어주는 과정을 반복 진행하였다.

#include <string>
#include <vector>
#include <utility>
#include <tuple>
#include <queue>
using namespace std;

int solution(vector<int> priorities, int location) {
    int answer = 0;

    queue<pair<int,int>> Q; // {초기 index, 우선 순위}
    priority_queue<int,vector<int>> PQ; // 현재 남은 대기열에서 가장 우선순위가 높은 작업의 우선순위

    int size = priorities.size();
    for(int i=0; i<size; i++){
        Q.push({i, priorities[i]});
        PQ.push(priorities[i]);
    }

    while(!Q.empty()){
        int idx, pr;
        tie(idx, pr) = Q.front(); Q.pop();
        if(PQ.top() > pr){
            Q.push({idx, pr});
        }
        else if(PQ.top() == pr){
            PQ.pop();
            answer++;
            if(idx == location) break;
        }
    }

    return answer;
}

다리를 지나는 트럭

문제

다리 위에 있는 트럭들을 Queue로 관리하고, 대기 중인 트럭들을 순차적으로 다리 위로 올리면서 작업을 진행한다.

Queue에서 트럭이 한 대씩 빠져나갈 때 마다 다리의 총 중량은 감소하므로, 큐에서 원소가 빠져나갈 때 마다 해당 무게를 기록할 수 있도록 무게 정보를 포함할 수 있도록 정의한다.

또한, Queue에 존재하는 원소들은 bridge_length 단위 시간 동안 존재하므로 생명 주기를 관리하기 위해 큐의 원소에 해당 정보를 포함시켰다.

즉, Queue에 들어가는 정보는 {남은 시간, 현재 트럭의 무게} 가 된다.

이 후, 대기중인 트럭들을 순회하면서

1. 해당 트럭이 다리위에 올라갈 수 있는 상태라면
   • 다리 위에 있는 트럭들을 모두 한칸 씩 앞으로 옮긴다
2. 해당 트럭이 다리위에 올라갈 수 없는 상태라면
   • 대기중인 트럭이 다리 위에 올라갈 수 있을 때 까지, 다리 위에 존재하는 트럭을 Front부터 하나씩 다리를 통과하게 만든다.

• 이 후, 현재 대기중인 트럭을 다리 위에 적재한다.

12번줄의 for-loop를 끝난 시점에서는, 현재 대기중인 트럭은 하나도 존재하지 않는다.

문제의 조건에 따라, 모든 트럭들이 다리를 통과한 시점을 구하기 위하여 다리 위에 존재하는 모든 트럭들이 다리를 통과한 시점의 시간을 구해야하므로, Queue에 존재하는 원소들을 모두 비운 뒤 시간을 계산한다.

+ 시간복잡도

$ 큐에 들어가는 원소의 개수 + 대기 중인 트럭의 개수 = truck_weights.size() $ 이다.

12번 줄의 for문은 최대 truck_weights.size() 만큼 반복하며, 한번의 루프마다 Queue의 size만큼 반복문($0 \leq i \leq N-1)$을 수행한다. Queue의 원소는 최악의 경우 $truck_weights.size() - i$ 만큼 반복하므로, 전체의 대략적인 시간복잡도는 $O(N^2)$로 볼 수 있다.

#include <string>
#include <vector>
#include <queue>
#include <tuple>
using namespace std;

int solution(int bridge_length, int weight, vector<int> truck_weights) {
    int answer = 0, totalWeight = 0;
    int size = truck_weights.size();

    queue<pair<int,int>> Q; // {남은 시간, 무게}
    for(int i=0; i<size; i++){
        int &target = truck_weights[i];
        if(target + totalWeight <= weight){
            // 이전에 다리 위에 올라온 트럭들의 남은 시간 감소
            int counter = Q.size();
            while(counter--){
                pair<int,int> item = Q.front(); Q.pop();
                if(item.first - 1 > 0)
                    Q.push({item.first - 1, item.second});
                else
                    totalWeight -= item.second;
            }
            answer += 1;
        }else{
            // totalWeight + target <= weight 가 될 때 까지 Queue의 원소를 pop
            while(totalWeight + target > weight && !Q.empty()){
                int t, w, counter = Q.size() - 1;
                tie(t, w) = Q.front(); Q.pop();
                while(counter--){
                    pair<int, int> item = Q.front(); Q.pop();
                    if(item.first - t > 0)
                        Q.push({item.first - t, item.second});
                }
                answer += t;
                totalWeight -= w;
            }
        }
        // 현재 트럭을 다리위에 올린다.
        Q.push({bridge_length, target});
        totalWeight += target;
    }
    // cond : [대기 중인 트럭들이 존재하지 않는 경우]
    // 다리 위에 올라와 있는 트럭들을 모두 처리한다.
    while(!Q.empty()){
        int t, w, counter = Q.size() - 1;
        tie(t, w) = Q.front(); Q.pop();
        while(counter--){
            pair<int, int> item = Q.front(); Q.pop();
            if(item.first - t > 0)
                Q.push({item.first - t, item.second});
        }
        answer += t;
    }

    return answer;
}

주식 가격 - level 2

문제

$i$번째 원소부터 $N-1$원소까지 탐색하는 Naive한 방법은 $O(N^2)$의 시간복잡도를 가지며, N의 범위가 최대 $100,000$인 것을 고려하였을 때 최적화가 필요하다는 것을 알 수 있다.

먼저, 불필요한 탐색을 제거할 수 있는 경우를 살펴보자.

f를 다음과 같이 정의하자.

$ f_i $: i번째 원소보다 뒤에 나오는 원소 중 감소하지 않는 원소의 개수

$ a_k < a_{k+1} < a_{k+2} $ 일 때, $f_{k} = f_{k+1} + 1$인 것은 자명하다. 이 경우, $f_k$ 각각을 구하지 않고 $f_{k+1}$ 값을 한번 구하는 것으로 $f_k$값을 구할 수 있다. 이는 귀납적으로 오름차순 원소를 유지하는 원소들의 집합에 대하여 만족하는 성질이다.

원소를 순차적으로 탐색한다는 점과 $f_k$를 구하기 위해 $f_{k+1}$ 항을 먼저 계산해야한다는 점에서 stack이라는 자료구조를 생각해볼 수 있다. 또한, 정의에 의하여 stack에 있는 원소들은 bottom -> top 까지 오름차순을 유지해야한다.

이와 같이 설계를 할 경우, 10번줄의 for문을 모두 수행할 동안 stack의 총 탐색횟수는 최대 N번이 되므로 전체 문제는 최대 2N번의 탐색횟수로 문제를 해결할 수 있다. $O(N)$

까다로웠던 부분은, prices 배열이 항상 오름차순으로 주어지지 않는다는 것이다. 이 경우, stack을 오름차순으로 유지해주되, 추가적인 작업들을 수행한다.

다음과 같은 상황을 생각해보자.

$a_1a_2a_3a_4a_5 = [1,\ 2,\ 3,\ 2,\ 3]$

스택에 들어가는 원소들을 오름차순으로 유지하였을 때, $i=4$까지 탐색을 하였을 때 stack에 존재하는 원소들은 다음과 같다 : $[1, 2, 2]$

우리는 이전에 카운팅을 위하여 $f_k = f_{k+1} + 1$을 해주었는데, 위 경우에서는 $a_3$의 원소인 3을 카운팅하지 못한다.

이를 해결하기 위하여 stack에 들어가는 원소를 다음과 같이 정의해보자.

stack<pair<int,int>> stk;

pair<int,int>: {해당 원소의 인덱스(정답 계산시 필요), 해당 원소가 삽입되기 이전 pop된 원소들의 개수}

위와 같이 정의한다면, 오름차순이 아닌 임의의 배열 prices에 대해서도 $f_k = f_{k+1} + count$로 일반화시켜 해결할 수 있다.

#include <string>
#include <vector>
#include <stack>
#include <tuple>
using namespace std;

vector<int> solution(vector<int> prices) {
    vector<int> answer(prices.size(), 0);
    stack<pair<int,int>> stk; // {idx, count}
    for(int i=0; i<prices.size(); i++){
        if(stk.empty() || prices[stk.top().first] <= prices[i]){
            stk.push({i, 1});
        }else{
            int counter = 1;
            while(!stk.empty() && prices[stk.top().first] > prices[i]){
                answer[stk.top().first] = counter;
                counter += stk.top().second;
                stk.pop();
            }
            stk.push({i, counter});
        }
    }
    int counter = 0;
    while(!stk.empty()){
        answer[stk.top().first] = counter;
        counter += stk.top().second;
        stk.pop();
    }

    return answer;
}