자바에서는 Stack은 별도 클래스로 제공하지만 Queue는 그렇지 않다. 따라서 Queue를 구현한 클래스를 사용해야한다.
메서드
- add : 객체를 큐에 저장
- poll : 큐에서 객체를 꺼내 반환
- peek : 삭제 없이 큐의 요소를 읽어 반환. 비어있으면 null을 반환.
- offer
- remove
- element
클래스
큐를 구현한 클래스들이 많다.
LinkedList가 대표적이고, 우선순위큐 (PriorityQueue)는 코딩테스트에서 자주 출제되는 것으로 안다.
프린터
문제
https://programmers.co.kr/learn/courses/30/lessons/42587
내 풀이 및 접근방법
코드
import java.util.*;
class Solution {
public int solution(int[] priorities, int location) {
int result = 0;
//index Queue 생성
Queue<Integer> indexQueue = new LinkedList<>();
Queue<Integer> taskQueue = new LinkedList<>();
//내림차순
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(Collections.reverseOrder());
for(int i=0; i < priorities.length; i++){
int addedNum = (i == location? 1 : 0);
indexQueue.add(addedNum);
taskQueue.add(priorities[i]);
priorityQueue.add(priorities[i]);
}
int cnt = 0;
while(taskQueue.peek() != null){
int peeked = taskQueue.poll();
int peekedIndex = indexQueue.poll();
if( peeked == priorityQueue.peek()){
cnt++;
priorityQueue.poll();
if(peekedIndex == 1){
//return cnt;
result = cnt;
break;
}
}else{ // peeked < max 일 경우 (priorityQueue.peek() 은 항상 max 이므로)
taskQueue.add(peeked);
indexQueue.add(peekedIndex);
}
}
// i : 0
// t : 1
// p : 1
//cnt : 5
return result;
}//method
}//class접근방법
indexQueue ( location에 해당하는 값인지 참조용 )
taskQueue
priorityQueue ( 최대값 참조용 )
이렇게 3개를 두고 품
주어진 로직을 따라가기위해서 priorityQueue를 사용했고
문제의 값을 return하기 위해서 indexQueue를 사용함.
이거 두개에 대한 아이디어를 찾는것이 힘들었고 자료구조가 Queue라는 것을 인식하는 것은 크게 문제가 되지 않았다.
다른사람 풀이
코드
https://programmers.co.kr/learn/courses/30/lessons/42587/solution_groups?language=java
접근방법
내 풀이에서 고민했던 2가지에 대한 접근방법을 달리했다.
indexQueue ( location에 해당하는 값인지 참조용 )
=> Class를 이용
priorityQueue ( 최대값 참조용 )
=> Arrays.sort( priorities )
새로운 큐를 만들 필요 없이, 각각 클래스를 사용하고 주어진 배열을 활용하면 되는 문제였다.
그밖에 출력 순서를 return 할때 cnt++를 이용한다는 점 등은 동일했다.
프린터
문제
https://programmers.co.kr/learn/courses/30/lessons/42583?language=java
내 풀이 및 접근방법
코드
import java.util.*;
class Solution {
public int solution(int bridge_length, int max_weight, int[] truck_weights) {
int answer = 0;
Queue<Truck> bridge_queue = new LinkedList<Truck>();
//현재 다리의 무게
// add remove에 따라
int bridge_weight = 0;
int i = 0;
//누적시간
int time = 1 ;
boolean isExceed ;
while(i < truck_weights.length){
isExceed = false;
//add 작업
int truck_weight = truck_weights[i];
// 넣었을때 초과하지않는경우 add
if( bridge_weight + truck_weight <= max_weight){
//맨 마지막 트럭인 경우
if(i == (truck_weights.length - 1) ){
//마지막 트럭이 다리를 통과하는 시간
int last_truck_pass_time = time + bridge_length;
answer = last_truck_pass_time;
break;
}
isExceed = true;
bridge_queue.add(new Truck(truck_weight, time));
i++;
bridge_weight+=truck_weight;
//여기서 time은 다음 트럭의 시간임
time++;
}
//초과하는 경우, 맨 앞에 있는 트럭이 빠지는 시간에 다시 진입 시도
time = (isExceed? time : bridge_queue.peek().start_time + bridge_length);
if(bridge_queue.peek()!=null){
if(time == (bridge_queue.peek().start_time + bridge_length)) {
bridge_weight -= bridge_queue.peek().weight;
bridge_queue.remove();
}
}
}
//모든 트럭을 다리에 건너도록 한 이후
// 현재 다리에 있는 모든 트럭들이 다리를 모두 건널때의 시간 return
return answer;
}
}
class Truck{
int weight;
int start_time;
public Truck(int weight, int time){
this.weight = weight;
this.start_time = time;
}
}접근방법
truck을 돌면서
넣었을때 초과하지않는 경우, bridge queue에 add
초과하는 경우, 맨 앞에 있는 트럭이 빠지는 시간으로 변경 후 다시 add 시도
결과값은 마지막 트럭이 지나는 시간
( == 마지막 트럭의 대기시간 + bridge의 length )
다른사람 풀이
코드
https://programmers.co.kr/learn/courses/30/lessons/42583/solution_groups?language=java
접근방법
truck_weight도 queue를 사용한다.
트럭의 start_time 대신 move 개념을 사용하였고, moving 메서드를 사용해서 이동하도록 하는 개념이 새로웠다.
로직이 깔끔함.
- 모든 트럭들을 한칸씩 이동시키고
- 빼야할 트럭은 빼고 (remove)
- 더해야할 트럭을 더하는 (add)
나는 더하고 빼는 과정에서 먼저하고 뒤에 하면서 하나씩 싱크가 안맞는 경우가 있었는데,
위 코드의 경우에는 위 과정을 한번의 반복에 시행해 단순하게 구현해서 그러한 문제가 발생하지 않음.
대신 시간 효율성은 내것이 더 좋지 않나 싶다.
내 코드 )
테스트 9 〉 통과 (1.03ms, 53.3MB)
다른사람 코드 )
테스트 9 〉 통과 (8.60ms, 52.7MB)
비교하자면 내 코드는 시간에, 다른 사람의 코드는 공간에 집중한 느낌이다.
마무리하며
프린터
이 문제는 오직 ‘자료구조’로서 큐를 사용하고 있을뿐.. 문제 푸는 핵심 아이디어가 큐인건 아님. ( 핵심 아이디어가 문제풀이력의 핵심 ). 다시 풀어볼만한 문제인듯하다.
다리를 지나는 트럭
이 문제 역시 자료구조로서 큐를 사용할뿐이다. 결국 모든 문제에서 가장 중요한 것은,
사용한 언어의 특성 활용 + 문제 해결 아이디어
가 아닐까.. ( 자바에서는 클래스 활용하는 것 등.. )
