프로그래머스 고득점 Kit 하루만에 뽀개기 - 2. 스택,큐 (Java, C++)

https://programmers.co.kr/learn/courses/30/parts/12081

프로그래머스

- 알고리즘 풀이로 C++를 주로 사용하다가 기업 코딩테스트를 위해 java 풀이를 학습하는 사람에게 도움이 될만한 포스트입니다. 알고리즘 적인 해설내용은 줄이고 C++에 익숙한 사람들이 Java 사용시 놓칠만한 내용 위주로 작성하고 있습니다.

 

- Stack<T> st = new Stack<>();
- Queue<T> q = new LinkedList<>();
- Queue<T> pq = new PrioiriyQueue<>(); // 최소힙(C++는 디폴트가 최대힙, 비교 연산자 초기값이 less<>). 헷갈릴 수 있음

# 문제 풀이

1. 기능 개발

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

코딩테스트 연습 - 기능개발

- 각 작업들에 대해서 걸리는 시간을 계산해서 순서대로 큐에 담아줍니다. 큐의 맨 앞 작업 기간보다 그 다음 작업기간이 짧거나 같으면 배포가 되지 않고 더 길면 배포가 되는 것이므로, 더 긴 작업기간 값이 나올 때까지 누적되는 작업 개수를 카운트해줍니다. 

// C++
#include <queue>
#include <vector>
using namespace std;

vector<int> solution(vector<int> progresses, vector<int> speeds) {
    vector<int> answer;
    queue<int> q;
    for (int i = 0; i < progresses.size(); ++i) {
        int rest = (100 - progresses[i]) % speeds[i] ? 1 : 0;
        int day = (100 - progresses[i]) / speeds[i] + rest;
        q.push(day);
    }
    // 7 3 9 -> 2 1
    while (!q.empty()) {  // 큐가 비면 종료 -> 큐가 비지 않았다(계속)
        int now = q.front();
        q.pop();
        int release = 1;
        while (!q.empty()) {  // first가 q.front보다 작으면 종료 - first가 q.front보다 같거나 크다 (계속)
            if (now >= q.front()) {
                q.pop();
                ++release;
            } else break;
        }
        answer.push_back(release);
    }

    return answer;
}

// java
import java.util.*;

class Solution {
    public List<Integer> solution(int[] progresses, int[] speeds) {
        List<Integer> ans = new ArrayList<>();
        
        int N = progresses.length;
        Queue<Integer> q = new LinkedList<>();
        for(int i = 0; i < N; ++i) {
            int rest = (100 - progresses[i]) % speeds[i];
            int day = (100 - progresses[i]) / speeds[i] + (rest > 0 ? 1 : 0);
            q.add(day);
        }
        
        // 7 3 9
        while(!q.isEmpty()) {
            int fi = q.poll();
            int release = 1;
            
            while(!q.isEmpty()) {
                int se = q.peek();
                if(fi >= se) {
                    q.remove();
                    ++release;
                } else break;
            }
            ans.add(release);
        }
        
		return ans;
    }
}

- Queue의 메서드 정리. 

https://javadoc.scijava.org/Java13/java.base/java/util/Queue.html

c++ queue에서 front(), pop()을 쓰듯이 java Queue에서는 add, remove를 동일하게 쓸 수 있다. 다만 NPE를 피하기 위해서 큐에 대한 연산이 실패했을 때 exception을 던지는 add, remove, element 대신 Null을 던지는 offer, poll, peek를 사용해줘도 된다. poll을 사용하면 변수에 top값을 초기화하면서 pop을 할 수 있다.

 

2. 프린터

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

코딩테스트 연습 - 프린터

- 제시된 규칙에 따라 대기 중인 문서 맨 처음부터 출력을 하는데, 만약 해당 문서보다 중요도가 높은 문서가 한 개라도 존재하면 대기열의 맨 후순위로 보내고 그다음 문서를 출력한다. 풀이에서는 대기열을 구현하는 큐, 가장 큰 우선순위부터 접근하는 최대힙을 선언해서 큐의 top과 최대힙의 top의 중요도가 같아서 그 것보다 큰 중요도의 문서가 없으면 pop해줄 수 있다. 문제에서는 특정 순서의 문서가 인쇄되는 순서를 리턴해준다. 

// C++
#include <queue>
#include <vector>
using namespace std;

int solution(vector<int> priorities, int location) {
    int answer = 0;
    queue<pair<int, int>> q;
    priority_queue<int> pq;
    
    for (int i = 0; i < priorities.size(); ++i) {
        q.push({priorities[i], i});
        pq.push(priorities[i]);
    }

    while (!q.empty()) {
        const auto& [first, second] = q.front();
        if (first == pq.top()) {
            answer++;
            if (second == location) {
                break;
            }
            q.pop();
            pq.pop();
        } else {
            q.pop();
            q.push({first, second});
        }
    }

    return answer;
}

import java.util.*;

class Solution {
    public int solution(int[] priorities, int location) {
        int ans = 0, N = priorities.length;
        
        Queue<List<Integer>> q = new LinkedList<>();
        Queue<Integer> pq = new PriorityQueue<>(); // 최대힙
        
        for(int i = 0; i < N; ++i) {
            List<Integer> pair = new ArrayList<>(); // priority, idx
            pair.add(priorities[i]);
            pair.add(i);
            q.add(pair);
            pq.add(-priorities[i]);
        }
        
        while(!q.isEmpty()) {
            List<Integer> peek = q.peek();
            if(peek.get(0) == -pq.peek()) {
                ++ans;
                if(peek.get(1) == location) break;
                q.remove();
                pq.remove();
            } else {
                q.remove();
                q.add(peek);
            }
        }
        return ans;
    }
}

- 자바에서는 따로 Pair 클래스를 선언하지 않고, List를 선언해서 넣어주었다
- 우선순위큐에 넣는 Integer값는 부호를 뒤집어서 절대값에 대해서 최대힙으로 사용하였고, 나중에 꺼낼때 다시 원래대로 부호를 뒤집으면 된다

3. 다리를 지나는 트럭

- 큐를 다리로 놓고, 큐의 사이즈가 다리의 길이와 같으면 다리의 맨 앞 차를 pop해주고, 현재 다리하중에서 빼준다. 
- 이번 순번 트럭이 무게제한으로 다리에 들어갈 수 없을 경우, 다리에 0을 푸쉬해줘서 차의 이동을 구현하였다. 
- 마지막 트럭까지 다리에 넣으면, 나머지 남은 거리인 다리길이를 모두 더해준다

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

int solution(int bridge_length, int weight, vector<int> truck_weights) {
    queue<int> q; // 올라와있는 다리큐
    int time = 0; // 0 ~
    int nowW = 0; // weight를 넘을 수 없음
    int tIdx = 0; // 0 ~ truck_weight.size() - 1
    
    while(1) {
        if(tIdx == truck_weights.size()) { // 0. 트럭 전부 넣음
            time += bridge_length;
            break;
        }
        
        if(q.size() == bridge_length) { // 1. 다리 자리가 꽉참
            nowW -= q.front();
            q.pop();
        }
        
        int tw = truck_weights[tIdx]; // 2. 다리 무게가 꽉참
        if(nowW + tw > weight) q.push(0);
        else { // 3. 다리에 넣을 수 있음
            q.push(tw);
            nowW += tw;
            ++tIdx;
        }
        
        ++time;
    }
    
    return time;
}

import java.util.*;

class Solution {
    public int solution(int bridge_length, int weight, int[] truck_weights) {
        int time = 0, nowW = 0, N = truck_weights.length;
        Queue<Integer> q = new LinkedList<>(); // bridge_length 이하로 유지
        
        for(int i = 0; i <= N;) {
            if(i == N) {
                time += bridge_length;
                break;
            }
            
            if(q.size() == bridge_length) {
                nowW -= q.poll();
            }
            
            int tw = truck_weights[i];
            if(nowW + tw <= weight) {
                q.add(tw);
                nowW += tw;
                ++i;
            } else {
                q.add(0);
            }
            
            ++time;
        }
        return time;
    }
}

 

4. 주식가격

- 딱히 어려운 것이 없는 문제여서 자바 풀이만 남긴다. 각 인덱스마다 이후 대소비교를 해서 해당 인덱스값이 작아졌으면 카운트를 중단한다

import java.util.*;

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