[Programmers] 프린터 - 스택/큐

import java.util.Collections;
import java.util.LinkedHashMap;
import java.util.LinkedList;
import java.util.Queue;

// 프린터 - 스택/큐
public class Printer {
	public int solution(int[] priorities, int location) {
		int q_element, order = 0;

		Queue<Integer> queue = new LinkedList<>(); // 프린터의 대기목록을 저장할 큐
		LinkedList<Integer> list = new LinkedList<>(); // 우선순위를 저장할 리스트 ; ArrayList는 원소를 삭제하면 인덱스가 계속 밀리므로 LinkedList보다 느리다.
		LinkedHashMap<Integer, Integer> map = new LinkedHashMap<>(); // key : 문서의 고유 번호 (0 ~ priorities.length - 1), value : 해당 문서의 우선순위

		for (int i = 0; i < priorities.length; i++) {
			list.add(priorities[i]);
			map.put(i, priorities[i]); // key : 문서의 고유 번호 (0 ~ priorities.length - 1), value : 해당 문서의 우선순위
			queue.offer(i); // 큐에 문서의 고유번호 (0 ~ priorities.length -1) 을 enqueue 
		}
		
		Collections.sort(list); // 우선순위 정렬
		while (!queue.isEmpty()) { // queue 가 empty일 때 까지 반복.

			q_element = queue.poll(); // queue 에서 하나씩 꺼냄 (FIFO)
			if (map.get(q_element) == list.get(list.size() - 1)) { // list.get(list.size() - 1) : 가장 높은 우선순위 (정렬된 우선순위를 저장한 list), map.get(q_element) : 해당 번호 문서의 우선순위. 위 두개가 같으면 프린터에서 출력
				order++; // 순서를 증가
				if (q_element == location) { // 문서의 번호와 location이 같을 때, 출력 순서를 알고자 하는 해당 문서가 출력 된것이므로 break;
					break;
				}
				list.remove(list.size() - 1); // 출력은 했으나 location과 다를 때, 즉 출력 순서를 알고자 하는 문서가 아닐 때 list에서 가장 높은 우선순위 (list.size() -1 번째 인덱스)를 list에서 제거
			} else {
				queue.offer(q_element); // queue에서 꺼낸 문서가 가장 높은 우선순위가 아닐때 dequeue 했던 값을 다시 큐에 enqueue
			}
		}

		return order; // 해당 문서의 출력 순서를 리턴
	}
	
	// 위 solution 메소드를 좀 더 간단하게 구현
	public int solution1(int[] priorities, int location) {
		int answer = 0;

		Queue<Integer> queue = new LinkedList<>();
		LinkedList<Integer> list = new LinkedList<>();

		for (int i = 0; i < priorities.length; i++) {
			list.add(priorities[i]);
			queue.offer(i);
		}

		Collections.sort(list);

		while (!queue.isEmpty()) {
			int ele = queue.poll();
			if (priorities[ele] == list.get(list.size() - 1)) {
				answer++;
				if (location == ele) {
					break;
				}
				list.remove(list.size() - 1);
			} else {
				queue.offer(ele);
			}
		}

		return answer;
	}

	public static void main(String[] args) {

		Printer s = new Printer();
		int[] arr1 = { 2, 1, 3, 2 };
		int[] arr2 = { 1, 1, 9, 1, 1, 1 };

		System.out.println(s.solution(arr1, 2)); // 1
		System.out.println(s.solution(arr2, 0)); // 5

	}

}

• ArrayList는 원소를 삭제하면 인덱스가 계속 밀리므로 LinkedList보다 느리다.