https://school.programmers.co.kr/learn/courses/30/lessons/42587
프로그래머스 - 코딩테스트 연습 - 스택/큐 -프린터
- 인쇄 목록에서 가장 중요도가 높은 문서를 먼저 출력
- 가장 앞에 있는 문서의 중요도보다 높은 문서가 뒤에 있으면 마지막으로 보냄
- 내가 인쇄를 요청한 문서가 몇 번째로 인쇄되는지를 구하기
주어진 인덱스에 있는 문서가 몇번째 인쇄인지 구하는 문제이다.
들어오는 배열은 문서를 구분할 수 있는 번호가 주어진 게 아니라, 문서의 중요도(출력 순서)가 들어있는 배열이다. 따라서 내가 구하려는 인덱스의 문서를 기록할 데이터가 필요하다고 생각했다.
우선 배열의 입력값은 1~9 까지의 양수이기 때문에, 내가 원하는 인덱스의 중요도를 -1로 변경하였다.
그렇게 되면 배열은 내가 원하는 인덱스의 값이 -1인 배열이 된다.
따라서 해당 인덱스의 원래 중요도가 필요하다. ( -1로 변경되었으므로)
이후에 인쇄를 할 때는 중요도가 -1이 들어오면(내가 원하는 인덱스의 중요도), 원래의 중요도와 해당 문서 뒤에 있는 중요도와 비교하고, 인쇄 여부를 결정한다.
예제 케이스 1
INPUT
priorities = [2,1,3,2]
location = 2
이때 priorities의 location 번째 값을 -1로 변경하고, 그때의 중요도를 priorValue 변수에 저장한다. 인쇄된 문서의 총 갯수를 count 로 둔다.
priorValue = 3
priorities = [2,1,-1,2] -> 큐에다 넣음
count = 0
큐에서 poll하고, 해당 값을 큐의 중요도 값들과 비교한다.
poll = 2
priorValue = 3
priorities = [1,-1,2]
count = 0
poll 한 값은 2지만, -1과 비교할 때에는 priorValue 와 비교해야 한다. 그것이 원래 중요도 이기 때문.
따라서 poll했던 값은 큐 뒤에 추가된다. (현재 인쇄할 수 없다)
priorValue = 3
priorities = [1,-1,2,2]
count = 0
poll 과정을 반복한다. poll된 값 1은 다시 큐 뒤에 추가된다.(인쇄불가)
priorValue = 3
priorities = [-1,2,2,1]
count = 0
poll 값이 -1 일때가 중요하다. 이 때는 큐에 있는 값들을 -1이 아닌 priorValue와 비교해야 한다.
poll = -1
priorValue = 3
priorities = [2,2,1]
count = 0
3이 큐의 모든 값보다 크므로 인쇄된다. -1이 인쇄되는 순간의 count를 리턴하면 된다.
count = 1
소스 코드
import java.util.Queue;
import java.util.LinkedList;
class Solution {
// 인쇄 목록에서 가장 중요도가 높은 문서를 먼저 출력
// 가장 앞에 있는 문서의 중요도보다 높은 문서가 있으면 마지막으로 보냄
// 내가 인쇄를 요청한 문서가 몇 번째로 인쇄되는지 출력
public int solution(int[] priorities, int location) {
Queue<Integer> queue = new LinkedList<>();
// 원하는 위치의 값을 -1 로 바꿔서 표시
// -1로 바꾼 값의 원래 값을 priorValue에 저장
int priorValue=priorities[location];
priorities[location]=-1;
for(int i=0;i<priorities.length;i++){
queue.add(priorities[i]);
}
//
// -1 // 1 9 1 1
// 인쇄된 문서의 갯수
int count=0;
//System.out.println(queue.toString());
while(!queue.isEmpty()){
// 맨 앞 종이의 중요도
int first = queue.poll();
//System.out.println("중요도: "+first+" "+queue.toString());
// 원하는 종이가 가장 앞에 왔을 때
if(first==-1){
// 만약 그 종이가 인쇄될 수 있는 순서이면
if(isMax(queue,priorValue,priorValue)){
//System.out.println("출력 완료");
return count+1;
}
// 큐에 중요도가 더 높은 문서가 있으면
else{
// 아직 출력할 수 없음
//System.out.println("중요도 "+first+" 인 문서 맨 뒤로 보냄");
queue.add(-1);
}
}
// 원하는 종이가 아닐 때
else{
// 중요도가 큐에 있는 값 중 가장 크면
if(isMax(queue,first,priorValue)){
// 해당 문서를 인쇄
//System.out.println("중요도 "+first+" 인 문서 인쇄");
count++;
}
// 중요도가 더 큰 문서가 뒤에 있으면
else{
//System.out.println("중요도 "+first+" 인 문서 맨 뒤로 보냄");
queue.add(first);
}
}
}
return count;
}
// poll 된 값이 큐에 있는 중요도 중 제일 높은지 판별하는 메소드
// priorValue( 출력을 원하는 문서의 중요도) 와도 비교가 필요하다. -1로 바꾸어졌기 때문
public boolean isMax(Queue<Integer> queue, int data, int priorValue){
if(data<priorValue){
return false;
}
for(int x : queue){
if(data<x){
return false;
}
}
return true;
}
}