오늘의 학습 키워드
</> 스택/큐
공부한 내용 본인의 언어로 정리하기
import java.util.*;
class Solution {
public int solution(int[] priorities, int location) {
//Key와 Value로 인덱스와 우선순위를 관리해야해서 추가/삭제가 편한 LinkedList이용
Queue<int[]> queue = new LinkedList<>();
//우선순위 크기 순서로 정렬(내림차순으로 정렬을 해야 앞쪽이 우선순위가 높은 값이 옴)
PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
//큐와 우선순위 초기화
for(int i = 0; i < priorities.length; i++){
// 큐에 [인덱스, 우선순위] 형태로 저장
queue.offer(new int[]{i, priorities[i]});
// 우선순위 큐에 우선순위 저장
pq.offer(priorities[i]);
}
int order = 0; //실행 순서 카운트
//queue가 다 비어있을때 까지 반복
while(!queue.isEmpty()){
int[] current = queue.poll(); //큐에서 프로세스 하나 꺼내기
//꺼낸 프로세스가 우선 순위가 높은 값인지 비교
if(current[1] == pq.peek()){
order++; // 실행 순서 증가
pq.poll();//우선 순위 큐에서 해당 우선순위 제거
//location의 순서 구하기
if(current[0] == location){
return order;
}
} else {
// 우선 순위가 더 높은 프로세스가 있다면 다시 큐에 넣기
queue.offer(current);
}
}
return 0;
}
}
오늘의 회고
다시 스택/큐 문제가 나오면서 아직 문법에 대해서 모르는게 많다는게 크게 다가온 하루였다.
아직 알아야할게 너무 많고 부족하다.
일단은 오늘 문제 풀이를 시작해보겠다.
오늘도 대략 1시간 정도 고민을 하면서 큰 값부터 뽑아 낼 수 있는 우선순위 큐랑 Key와 Value를 활용해서 순서를 저장하고 이용하면 좋겠다라고 생각했고 이것을 활용할 방법을 찾았다.
그래서 일단 위의 2개를 만들어주었다.
스택/큐 문제였기 때문에 큐와 우선순위 큐를 만들어 주었다.
알아보다 보니 LinkedList가 추가/삭제가 쉽다고 보았고 priorities값에 Key를 부여해주어야 겠다고 생각했기 때문에 아래와 같이 만들었다.
Queue<int[]> queue = new LinkedList<>();
PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());이후 priorities 값에 key를 부여해줘서 초기화를 시켜준다.
그리고 우선순위 큐에 우선순위를 저장해준다.
for(int i = 0; priorities.length; i++){
queue.offer(new int[]{i, priorities[i]});
pq.offer(priorities[i]);
}이제 운영체제가 프로세스를 관리하는 규칙에 따라 메인루프를 만들어야 한다.
그래서 queue가 모두 제거될 때 까지 반복해서 순서를 구하고 검증하는 것들이 필요했다.
while(!queue.isEmpty()){
}매번 현재 큐를 비교해서 진행해야하기 때문에 queue의 값을 꺼내서 넣어줄 current 객체를 하나 만들어 준다.
int[] current = queue.poll();꺼낸 큐가 우선순위에 pq에서 가장 높은 값인지 검증하고 맞다면 우선 순위 큐에서 해당 큐를 제거하고 아니라면 다시 큐에 넣어준다.
if(current[1] == pq.peek()){
pq.poll();
} else {
queue.offer(current);
}진행 순서는 완료 되었고, location의 순서를 구하기 위해서 코드를 추가해 준다.
int order = 0;검증하는 if문 안에 실행순서를 증가 시키고 현재값이 location과 같다면 순서를 반환하주는 방식으로 진행하도록 했다.
if(current[1] == pq.peek()){
order++;
pq.poll();
}
if(current[0] == location){
return order;
}그리고 마지막에는 컴파일을 위해서 return을 할 필요가 있었는데 이 값을 임의로 0으로 설정해 주었다. 하지만 지금 회고하면서 생각해보니 해당될 수 없는 값인 음수로 해놓았으면 어땠을까 생각이 든다.
AI 코드리뷰
현재 코드의 장점
LinkedList와PriorityQueue를 적절히 사용하여 문제를 해결하고 있습니다.- 코드가 간결하고 이해하기 쉽습니다.
- 주어진 문제를 정확히 해결하고 있습니다.
현재 코드의 단점
PriorityQueue를 전체 우선순위에 대해 생성하고 있어, 메모리 사용량이 다소 높을 수 있습니다.- 매 반복마다
PriorityQueue의peek()연산을 수행하고 있어, 약간의 성능 저하가 있을 수 있습니다.
시간 복잡도
- 큐에 모든 요소를 추가하는 시간 복잡도: O(n)
- 우선순위 큐에서 가장 높은 우선순위를 찾는 시간 복잡도: O(log n)
- 최악의 경우, 모든 요소를 큐에 다시 넣는 과정이 반복될 수 있으므로,
최종 시간 복잡도는 O(n^2 log n)
개선된 코드 제안
import java.util.*;
class Solution {
public int solution(int[] priorities, int location) {
Queue<int[]> queue = new LinkedList<>();
for(int i = 0; i < priorities.length; i++){
queue.offer(new int[]{i, priorities[i]});
}
Arrays.sort(priorities); // 우선순위 정렬
int order = 0;
while(!queue.isEmpty()){
int[] current = queue.poll();
if(current[1] == priorities[priorities.length - 1 - order]){
order++;
if(current[0] == location){
return order;
}
} else {
queue.offer(current);
}
}
return 0;
}
}
개선된 버전의 장점
- 메모리 사용 최적화: 별도의 우선순위 큐를 사용하지 않고, 우선순위 배열을 정렬하여 비교함으로써 메모리 사용을 줄였습니다.
- 제네릭 사용:
Queue<int[]>를 사용하여 데이터 타입의 안정성을 높였습니다. - 단순화된 로직: 우선순위 큐와 큐 간의 불필요한 데이터 이동을 제거하여 로직을 단순화하였습니다.
개선된 버전의 단점
- 우선순위 배열 정렬 비용:
Arrays.sort를 사용하여 우선순위를 정렬하므로O(n log n)의 추가 비용이 발생합니다. - 가독성 저하: 일부에서는 이전 코드보다 덜 직관적으로 느껴질 수 있으며, 정렬된 우선순위 배열과 비교하는 방식이 덜 명확하게 보일 수 있습니다.
시간 복잡도
- 우선순위 정렬의 시간 복잡도: O(n log n)
- 큐에서의 모든 작업 처리 시간 복잡도: O(n)
- 최종 시간 복잡도는 O(n log n)입니다.
내일 공부할 것 :
내일 스택과 큐에 대해서 정리해서 기록을 해야되겠다. 스택과 큐 안에서도 여러가지 기능이 있는 것으로 알고있고 오늘 공부하면서 태블릿에 살짝 정리해 놓은것도 있는데 생각보다 많이 커질거 같다.
문제
https://school.programmers.co.kr/learn/courses/30/lessons/42587
