봄봄.devlog
백준 | 1966번 :: 프린터 큐 본문
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 |