[프로그래머스-자바] 스택/큐 Stack/Queue

기능개발

• 다양한 풀이 방법이 있는 문제지만 큐를 활용해보기로 했다.
• Math.ceil()이라는 메소드로 올림을 할 수 있다.
• 각 남은 날을 큐에 넣는다.
• 먼저 첫번째 날을 뽑아내고 큐가 비지 않을 때까지 다음꺼를 뽑고 비교해서 앞의 날이 더 크면 count를 ++한다. 뒤 값이 더 클 경우 그냥 count를 arraylist에 추가하고 cont =1로 초기화해준다. 앞 값을 현재 값으로 맞춰야 한다.
• 그렇게 정리된 arraylist값을 answer[]에 넣어준다.
• 다양한 방법이 있으니 다시 풀어 볼 것!

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

public class PerfomanceDevelop {
    public int[] solution(int[] progresses, int[] speeds) {

        Queue<Integer> queue = new LinkedList<>();
        ArrayList<Integer> result = new ArrayList<>();
        for (int i = 0; i < progresses.length; i++) {
            int day = (int) Math.ceil((double) (100 - progresses[i]) / speeds[i]);
            queue.offer(day);
        }
        int prev = queue.poll();
        int count = 1;
        while (!queue.isEmpty()) {
            int now = queue.poll();
            if (prev >= now) {
                count++;
            } else {
                result.add(count);
                count = 1;
                prev = now;
            }
        }
        result.add(count);

        int[] answer = new int[result.size()];
        for (int i = 0; i < answer.length; i++) {
            answer[i] = result.get(i);
        }

        return answer;
    }
}

프린터

• 인덱스와 우선순위 큐들을 잘 관리하기 위해 두 개의 arraylist로 관리
• Collections.max()를 이용해 ArrayList중 가장 큰 값을 쉽게 찾는다.

import java.util.ArrayList;
import java.util.Collections;

public class Printer {
    public int solution(int[] priorities, int location) {
        int answer = 0;
        ArrayList<Integer> prior = new ArrayList<Integer>();
        ArrayList<Integer> index = new ArrayList<>();

        for(int i=0; i<priorities.length;i++){
            prior.add(priorities[i]);
            index.add(i);
        }

        int count = 0;
        while(true){
            int idx = index.get(0);
            int p = prior.get(0);
            index.remove(0);
            prior.remove(0);

            if(prior.size() == 0){
                answer += count +1 ;
                break;
            }

            if(Collections.max(prior) > p){
                prior.add(p);
                index.add(idx);
            }else{
                count += 1;
                if(location == idx ){
                    answer = count;
                    break;
                }
            }
        }

        return answer;
    }
}

 

다리를 지나는 트럭

• for구문 안에서 트럭 하나씩 큐에 넣어서 진행한다.
• 큐에 아무 것도 없을 때 넣고 시간(answer)을 ++한다. 현재 무게도 더해준다.
• 큐 크기가 다리 길이일 경우 poll()해준다.
• 현재 무게에 다음 트럭 무게를 더해도 괜찮을 경우 큐에 더해주고, 현재 무게에도 더해주고, answer++해준다.
• 마지막으로 아무것도 할 수 없을 경우 큐에 0을 넣어주고 시간++해준다.

import java.util.LinkedList;
import java.util.Queue;

public class Truck {
    public int solution(int bridge_length, int weight, int[] truck_weights) {
        int answer = 0;
        Queue<Integer> q = new LinkedList<>();

        int current_weight = 0;
        for(int truck : truck_weights){
            while(true){
                if(q.isEmpty()){
                    q.add(truck);
                    answer++;
                    current_weight += truck;
                    break;
                }else if(q.size() == bridge_length){
                    current_weight -= q.poll();
                }else if(current_weight + truck <= weight){
                    q.add(truck);
                    current_weight += truck;
                    answer++;
                    break;
                }else{
                    q.offer(0);
                    answer++;
                }
            }
        }
        return answer + bridge_length;
    }
}

주식가격

• 딱히 스택이나 큐를 사용하지 않고 푼 문제였다.

public class StockPrice {
    public int[] solution(int[] prices) {
        int[] answer = new int[prices.length];
        answer[prices.length-1] = 0;

        for(int i=0;i<prices.length-1;i++){
            int count = 0;
            for(int j=i+1;j<prices.length;j++){
                if(prices[i] <= prices[j]){
                    count++;
                }else{
                    count++;
                    break;
                }
            }
            answer[i] = count;
        }
        return answer;
    }
}