백준 | 1966번 :: 프린터 큐

https://www.acmicpc.net/problem/1966

1966번: 프린터 큐

🎈 My 문제 풀이

 

문서도의 '중요도'를 확인. 나머지 문서들 중 현재 문서보다 중요도가 높은 문서가 하나라도 있으면 뒤로 보낸다. 그렇지 않으면 바로 인쇄.  어떤 한 문서가 몇 번째로 인쇄되는지 알아내는 것.

 

- 각 문서의 인덱스와 중요도 값을 저장할 수 있는 Document 클래스를 만들고, 중요도를 저장할 수 있는 ArrayList 배열을 따로 만들어서 관리했다.

- 그리고 나서 중요도 ArrayList 배열을 정렬하고, 가장 앞에 있는 문서의 중요도가 중요도 배열의 마지막 인덱스 값보다 작은 경우 바로 인쇄하지 못하고 뒤로 보내도록 처리하였다. 

- 만약 가장 앞의 문서의 중요도가 중요도 배열의 마지막 인덱스 값과 같다면 이보다 큰 중요도가 없다는 것을 의미하므로 중요도 배열에서 해당 값을 제거하고, 해당 문서도 인쇄한다.

- 인쇄할 때 마다 count를 하고  찾으려고 하는 어떤 한 문서의 위치와 인쇄하는 문서의 위치가 같으면  count를 출력하고 프로그램을 종료한다.

 

- 문서의 idx와 중요도를 다 따져야 하는 문제이므로 이를 잘 처리하는 방법

 

🎈 다른 사람 문제 풀이

 

- max 중요도 값을 구하고 그 값보다 가장 앞의 문서의 중요도가 작으면 뒤로 보내기

 

static int maxPriority(ArrayDeque<Document> queue) {
	int max = 0;
    for(Document doc : queue) 
    	if(max < doc.priority) max = doc.priority;
    return max;
}

 

🎈 소스 코드

public class Q1966_1 {

	public static class Document {
		int idx;
		int value;

		public Document(int idx, int value) {
			this.idx = idx;
			this.value = value;
		}
	}

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		int T = sc.nextInt();

		while(T-->0) {

			int n = sc.nextInt(); // 문서의 수
			int location = sc.nextInt(); // 특정 문서의 위치
			int cnt = 0;

			Queue<Document> queue = new LinkedList<>();
			List<Integer> list = new ArrayList<>(); // 중요도 저장

			for(int i=0; i<n; i++) {
				int tmp = sc.nextInt();
				queue.add(new Document(i, tmp));
				list.add(tmp);
			}

			Collections.sort(list);

			while(!queue.isEmpty()) {
				Document document = queue.poll();
				if(list.get(list.size()-1) > document.value) { // 현재 문서 중요도가 떨어지면
					queue.add(document); // 뒤로 보내기
				} else {
					cnt += 1;
					list.remove(list.size()-1); // 마지막 값 제거
					if(document.idx == location) break;
				}
			}
			System.out.println(cnt);
		}
	}
}