이중우선순위큐

작성일: 2024-10-25

문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/42628

접근 방식

• 리스트를 이용해서 유연하게 데이터를 관리한다.
• 문자열 배열의 문자열을 문자열 배열로 변환한다.
  • 문자열 배열의 0번째가 I인 경우, 1번을 리스트에 넣는다.
  • 0번이 D, 1번이 1인 경우, 리스트에서 맨 마지막 값을 제거한다.
  • 0번이 D, 1번이 -1인 경우, 리스트의 맨 처음 값을 제거한다.
• 위의 로직을 진행하고, 리스트를 오름차순 정렬한다.
• 만약 리스트가 비어있다면 {0, 0}을, 비어있지 않다면 {최댓값, 최솟값}을 리턴한다.

결과

소스 코드

import java.util.*;

class Solution {
    public int[] solution(String[] operations) {
        int[] answer = {};
        List<Integer> list = new ArrayList<>();

        for(String o:operations){
            String tmp[] = o.split(" ");
            if(tmp[0].equals("I")){
                list.add(Integer.parseInt(tmp[1]));
            } else if(tmp[0].equals("D") && tmp[1].equals("1") && !list.isEmpty()){
                list.remove(list.size()-1);
            } else if(tmp[0].equals("D") && tmp[1].equals("-1") && !list.isEmpty()){
                list.remove(0);
            }
            Collections.sort(list);
        }

        return list.isEmpty() ? new int[]{0, 0} : new int[]{list.get(list.size()-1), list.get(0)};
    }
}

다른 접근 방식

문제 이름이 우선순위큐이긴 하지만, 코딩 테스트 연습을 하는 것이기 때문에

우선순위큐를 사용하지 않았다. ㅋㅋㅋ

우선순위큐를 이용하면, 로직은 거의 똑같고, 사용하는 자료구조가 List에서 PriorityQueue로 변경된다.

우선순위큐

import java.util.*;

class Solution {
    public int[] solution(String[] operations) {
        Queue<Integer> min = new PriorityQueue<>();
        Queue<Integer> max = new PriorityQueue<>(Collections.reverseOrder());

        for(String o:operations){
            String tmp[] = o.split(" ");
            if(tmp[0].equals("I")){
                min.offer(Integer.parseInt(tmp[1]));
                max.offer(Integer.parseInt(tmp[1]));
            } else if(o.equals("D 1") && !max.isEmpty()){
                min.remove(max.poll());
            } else if(o.equals("D -1") && !max.isEmpty()){
                max.remove(min.poll());
            }
        }
        return max.isEmpty() && min.isEmpty() ? new int[]{0, 0} : new int[]{max.poll(), min.poll()};
    }
}

알게 된 점

없음.