[코딩테스트 고득점 Kit] 스택/큐

문제 링크

기능개발

import java.util.*;

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

        for (int i=0; i<progresses.length; i++) {
            queue.add((int)(Math.ceil((100 - progresses[i]) / (double)speeds[i])));
        }

        List<Integer> answer = new ArrayList<>();
        while (!queue.isEmpty()) {
            int num = queue.poll();
            int cnt = 1;

            while (!queue.isEmpty() && num>=queue.peek()) {
                cnt++;
                queue.poll();
            }
            answer.add(cnt);
        }
    
        return answer.stream().mapToInt(Integer::intValue).toArray();
    }
}

우선 배포가 될 때까지의 날짜를 큐에 저장(올림함수인 Math.ceil사용)
큐가 빌 때까지 while문을 돌리고 FIFO이므로 제일 먼저 들어간 값을 빼와서 num에 저장 후 큐에서 값을 계속 빼서 num보다 작으면 cnt를 하나씩 올린다.
num보다 크면 cnt를 answer에 저장하고 이것을 반복한다.
List인 answer를 stream().mapToInt(Integer::intValue).toArray() 를 사용해 int[]형으로 바꿔 return해준다.

프린터

import java.util.*;

class Solution {
    public int solution(int[] priorities, int location) {
        int answer = 1;
        Queue<Integer> queue = new PriorityQueue<>(Collections.reverseOrder());
        
        for(int p : priorities) {
            queue.add(p);
        }
        
        while(!queue.isEmpty()) {
            for(int i=0; i<priorities.length; i++) {
                if(priorities[i] == (int)queue.peek()) {
                    if(i == location) return answer;
                    queue.poll();
                    answer++;
                }
            }
        }
        return answer;
    }
}

프린터는 문제에도 나와있듯이 우선순위를 사용하는 문제다.
그래서 큐 대신 우선순위 큐, PriorityQueue를 사용했다.
우선순위를 내림차순으로 큐에 저장해준 뒤 큐가 빌 때까지 while문을 실행한다.
index를 이용한 for문을 돌려서 큐의 peek()값과 같으면 poll()해주고 answer(반환 순서)++해준다. → 이미 탐색한 index는 자동으로 뒤로 밀리게 됨 👍
이 때 구해야하는 location값이면 바로 answer값을 return 해주게 된다.

다리를 지나는 트럭

import java.util.*;
/*
* queue.size가 bridge_length와 같으면 poll, 무게--
* 대기 트럭을 다리 위에 올렸을 때 weight을 넘으면 0을 add, 시간++
* 
* 위의 두 경우가 아닌 경우 트럭을 올림, 무게++ 시간++ 대기트럭 접근하는 idx++
* 마지막 대기 트럭이 올라가면 다리 길이만큼 더해준 값 return
*/
class Solution {
    public int solution(int bridge_length, int weight, int[] truck_weights) {
        Queue<Integer> queue = new LinkedList<>();
        int total_weight = 0;
        int answer = 0;
        int idx = 0;
        
        while(idx!=truck_weights.length) {
            
            if(queue.size() == bridge_length) {
                total_weight -= queue.poll();                
            }
            
            if(total_weight+truck_weights[idx] > weight) {
                queue.add(0);
                answer++;
                continue;
            }
            queue.add(truck_weights[idx]);
            total_weight += truck_weights[idx];
            answer++;
            idx++;
        }
    
        return answer + bridge_length;
    }
}

같이 스터디하는 분이 맨 위에 코드에 대한 설명을 적어놓는 걸 보고 한번 적어봤다. 코드 짤때 시간이 덜 걸리고 깔끔하게 코드를 적는데에 굉장히 좋은 방법인 것 같다!!

주식가격

import java.util.*;

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

스택큐를 사용하지 않고 for문 2개를 돌려도 효율성이 통과됐다...!
좀 더 빠른 방법이 있지않을까 하고 map으로 값을 저장해봤는데 오히려 시간이 더 걸려서 원래 코드를 가져왔다.
스택큐를 사용해서 더 빠른 방법이 생각이 안나서 일단...

---

예전부터 많이 사용하던 알고리즘이고 레벨도 모두 2단계여서 대체적으로 쉽게 푼 것 같다. 👍