https://school.programmers.co.kr/learn/courses/30/lessons/42587?language=java
처음 풀이
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
public class 프린터 {
Integer[] dump = {0, -1};
public int solution(int[] priorities, int location) {
//요청리스트
Queue<Integer[]> reqList = new LinkedList<>();
//실제 인쇄리스트
List<Integer> printList = new ArrayList<>();
//{중요도, 인덱스}형태의 Integer배열을 Queue구조로 저장
int nodeIdx = 0;
for(int priority : priorities) {
Integer[] newNode = {priority, nodeIdx++};
reqList.add(newNode);
}//for end
//중요도를 정렬함 (여기선 오름차순)
//내가 poll한 프린트의 중요도가 남아있는 프린트 요청 리스트에서 가장 높은지 확인하기 위해
Arrays.sort(priorities);
Integer[] top = dump;
//queue에서 poll한 요소의 중요도와, sort한 priorities배열의 뒤 요소(내림차순 정리했으므로)를 비교
int index = priorities.length-1;
while(printList.size()<priorities.length) {
top = reqList.poll();
if(top[0]==priorities[index]) {
//현재 top의 중요도와 priorities배열 값이 같으므로
//printList에 해당 top의 location(index)를 add
printList.add(top[1]);
//현재 index의 priorities요소가 print됐으므로
//그 다음 index로 이동 (내림차순 정리이므로 -1)
index--;
} else {
//다르다면, 현재 top의 중요도가 남은 요청 리스트의 중요도 중에서
//가장 높은 것이 아니므로 요청 리스트의 맨 뒤로 add
reqList.add(top);
}
}
int i = 0;
for(i=0; i<printList.size(); i++) {
if(printList.get(i)==location) break;
}//for end
return i+1;
}
}
다른 풀이
우선순위 큐 사용
import java.util.Collections;
import java.util.PriorityQueue;
import java.util.Queue;
class Solution {
public int solution(int[] priorities, int location) {
int answer = 0;
//Max heap
Queue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
//중요도 값을 pq에 add
for(int priority : priorities) {
pq.add(priority);
}//for end
//pq가 빌때까지 반복
while(!pq.isEmpty()) {
//pq에서 나오는 값과 같은 경우 탐색
for(int i=0; i<priorities.length; i++) {
//값이 같다면 출력!
if(pq.peek()==priorities[i]) {
pq.poll();
answer++;
//값이 같고, 위치도 같다면 answer 반환
if(i == location) return answer;
}
}//for end
}//while end
return answer;
}
}
'자료구조 & 알고리즘 > 문제풀이' 카테고리의 다른 글
땅따먹기 - 프로그래머스 (Java, Level 2) (0) | 2022.08.05 |
---|---|
디스크 컨트롤러 - 프로그래머스 (Java, Level 3) (0) | 2022.08.05 |
트리 순회 - 백준 1991 (Java) (0) | 2022.08.03 |
길 찾기 게임 - 2019 Kakao Blind Recruitment (Java, Level 3) (0) | 2022.07.30 |
키 순서 - 백준 2458 (Java) (0) | 2022.07.26 |
댓글