728x90
[Java] 프로그래머스 : 프로세스
https://school.programmers.co.kr/learn/courses/30/lessons/42587
접근
2번째 테스트 케이스를 보면 가장 처음 인덱스에 있는 값이 5번째로 실행되는 것을 확인할 수 있다.
9다음 1이 다음 우선순위가 되도록 하기 위해서 가장 먼저 떠올린 것은, priorities를 내림차순 정렬한 배열을 하나 더 만드는 것이었다.
큐에는 priorities 원본 배열 값을 전부 집어 넣고, 내림차순된 배열의 값과 큐의 특정 값이 일치하는 경우 answer를 하나씩 올리고,
만약 location번째의 값이었을 경우 정답을 출력할 수 있도록 구현하였다.
import java.util.*;
class Position {
int priority;
int idx;
Position(int priority, int idx) {
this.priority = priority;
this.idx = idx;
}
}
class Solution {
public int solution(int[] priorities, int location) {
int answer = 0;
Queue<Position> q = new LinkedList<>();
int[] temp = Arrays.copyOf(priorities, priorities.length);
Integer[] priArr = Arrays.stream(temp).boxed().toArray(Integer[]::new);
Arrays.sort(priArr, Collections.reverseOrder());
for (int i = 0; i < priorities.length; i++) {
q.offer(new Position(priorities[i], i));
}
int idx = 0;
while (!q.isEmpty()) {
Position pos = q.poll();
if (pos.priority == priArr[idx]) {
answer++;
idx++;
if (pos.idx == location) {
break;
}
}
else {
q.offer(pos);
}
}
return answer;
}
}
그러나 위의 방법은 큐에 들어갈 값들의 위치를 기억하기 위한 메모리가 필요할 뿐만 아니라, 내림차순 배열을 만들기 위해 배열 복사까지 해야했기 때문에 개선이 필요했다.
먼저, 내림차순 배열을 하나 더 만드는 부분을 우선순위 큐를 선언하여 자동으로 내림차순 되는 큐를 만드는 방식으로 변경했다.
기존에는 배열을 내림차순 한 후, 큐를 계속 순회하면서 값이 일치하는 경우를 찾았으나, 이번에는 큐가 자동으로 내림차순 정렬되어 있기 때문에 기존 배열에서 location에 해당하는 값이 무엇인지 훨씬 수월하게 찾을 수 있었다.
import java.util.*;
class Solution {
public int solution(int[] priorities, int location) {
int answer = 0;
PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
for (int p : priorities) {
pq.add(p);
}
while(!pq.isEmpty()) {
for (int i = 0; i < priorities.length; i++) {
if (priorities[i] == pq.peek()) {
pq.poll();
answer++;
if (i == location) {
return answer;
}
}
}
}
return answer;
}
}
728x90
'알고리즘 문제 풀이 > 정렬' 카테고리의 다른 글
[Java] 프로그래머스 : 튜플 (0) | 2023.09.11 |
---|---|
[Java] 프로그래머스 : 귤 고르기 (0) | 2023.08.27 |