봄봄.devlog

백준 | 1966번 :: 프린터 큐 본문

Algorithm/백준

백준 | 1966번 :: 프린터 큐

jihyun03 2020. 8. 10. 13:42

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

 

1966번: 프린터 큐

문제 여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료��

www.acmicpc.net

🎈 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);
		}
	}
}

 

'Algorithm > 백준' 카테고리의 다른 글

백준 7576번 :: 토마토 (BFS)  (0) 2020.08.23
백준 11047번 :: 동전 0번 (그리디 알고리즘)  (0) 2020.08.16
백준 | 10799번 :: 쇠막대기  (0) 2020.08.09
백준 | 10845번 :: 큐  (0) 2020.08.09
백준 | 9012번 :: 괄호  (0) 2020.08.09
Comments