프로그래머스 스택/큐

문제

풀이

import java.util.*;

class Solution {
    public int[] solution(int[] progresses, int[] speeds) {
        Queue<Integer> queue = new LinkedList<>();
        List<Integer> list = new ArrayList<>();

        for (int i = 0; i < speeds.length; i++) {
            double remain = (100 - progresses[i]) / (double) speeds[i];
            int date = (int) Math.ceil(remain); // 작업의 남은 일수

            if (!queue.isEmpty() && queue.peek() < date) { // 현재 작업의 남은 일수가 큐에 있는 작업의 남은 일수 보다 클 때
                list.add(queue.size()); // 큐 사이즈(작업의 개수)를 배포 개수 리스트에 추가
                queue.clear(); // 큐 비우기
            }

            queue.offer(date); // 현재 작업의 남은 일수를 큐에 추가
        }

        list.add(queue.size()); // 남아있는 작업의 개수 추가시키기

        int[] answer = new int[list.size()];

        for (int i = 0; i < answer.length; i++) {
            answer[i] = list.get(i); // 정답 배열에 추가
        }

        return answer;
    }
}

큐를 이용해서 해결할 수 있는 문제다.

결과

문제

풀이

import java.util.*;

class Solution {
    boolean solution(String s) {
        boolean answer = true;
        Stack<Character> stack = new Stack<>();

        for(char x : s.toCharArray()) {
            if(x == '(') {
                stack.push(x);
            } else {
                // 닫는 괄호가 많은 상황
                if(stack.isEmpty()) {
                    return false;
                }
                stack.pop();
            }
        }

        // 여는 괄호가 많은 상황
        if(!stack.isEmpty()) {
            return false;
        }

        return answer;
    }
}

결과

문제

풀이

import java.util.*;

class Solution {
    public int solution(int[] priorities, int location) {
        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder()); // 중요도가 높은 순으로 저장됨
        int answer = 0;
        
        for (int i = 0; i < priorities.length; i++) {
            pq.add(priorities[i]);
        }
        
        while (!pq.isEmpty()) {
            for (int i = 0; i < priorities.length; i++) {
                if (priorities[i] == pq.peek()) {
                    if (i == location) {
                        answer++;
                        return answer;
                    }
                    pq.poll();
                    answer++;
                }
            }
        }
        return -1;
    }
}

결과

문제

풀이

import java.util.*;

class Solution {
    public int solution(int bridge_length, int weight, int[] truck_weights) {
        Queue<Integer> queue = new LinkedList<>();
		int sum = 0;
		int time = 0; 

		for(int i = 0; i < truck_weights.length; i++) { 
			int truck = truck_weights[i];
			while(true) {
				if(queue.isEmpty()) { // 다리 위에 어떤 트럭도 없음
					queue.add(truck);
					sum += truck;
					time++; 
					break;
				} else if(queue.size() == bridge_length) { // 다리 길이만큼 큐에 트럭이 찬 경우 
					sum -= queue.poll(); // 다리 끝에 도달한 트럭 빼주기
				} else { // 큐가 안 찼을 경우
					// weight 값을 넘지 않는다면 새로운 트럭을 다리에 올리기 
					if(sum + truck <= weight) {
						queue.add(truck);
						sum += truck;
						time++;
						break;
					} else { // 넘을 경우 0을 추가해서 큐에 있는 트럭이 다리를 건널 수 있게 함
						queue.add(0);
						time++;
					}
				}
			}
		}

        // 마지막 남은 트럭이 다리 길이만큼 지나가야하기에 다리 길이만큼 더해줌
		return time + bridge_length; 
    }
}

결과

문제

풀이

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;
    }
}

결과