(24.06.03)[8주차] PriorityQueue

ArrayList 자료구조형만을 쓰는것을 탈피하기 위해 그냥 넘어갈 수 있는 자료구조를 확용하는 연습과 학습

---

COKE KATA 의 내용중 최솟값 또는 최댓값을 자료형 구조에서 제거를 해야할때, 사용하는 자료구조에 관한 내용을 찾아보고 정리, 학습

PriorityQueue

• Queue 인터페이스 중에선 우선순위 priority 순서대로 꺼내는 Queue
  • 데이터를 이진 트리인 heap 으로 저장하기 때문
• 단! Priority를 판단해야하기 때문에 Queue 와 다르게 null 허용이 안됨
  • TreeSet과 유사
• 자연순서=natural order 를 기본으로 하기 때문에, 숫자로 된 자료는 오름차순, 문자열일 경우엔 알파벳 순으로 우선순위를 부여
• offer()은 상관이 없지만 poll() 메서드일 경우 FIFO 구조의 기존 Queu와 달리, 가장 최솟값이 나오면서 구조에서 삭제가 됨

기존 코드

• 직접 짠 자료구조의 새로운 값이 추가가될 때, 자료 중 최솟값을 제거하는 코드
•  

public class Main {
    public static int[] main(String[] args) {
        int k = 3;
        int[] score = {10, 100, 20, 150, 1, 100, 200};

        int[] answer = new int[score.length];

        ArrayList<Integer> scoreList = new ArrayList<>();
                for (int i = 0; i < score.length; i++) {
                    scoreList.add(score[i]);
                    Collections.sort(scoreList);
                    if (scoreList.size() > k) {
                        scoreList.remove(0);
                        answer[i] = scoreList.get(0);
                    } else {
                        answer[i] = Collections.min(scoreList);
            }
        }
       return answer;
    }

• 최솟값을 지우면서 자료구조의 size를 유지해야했기 때문에, ArrayList로 설정
• Collections 클래스의 sort() 메서드를 사용하여 오름차순으로 정렬 -> remove() 메서드를 통해 0번 인덱스값 = 최솟값 삭제
  • List에 추가된 자료를 포함해서 계속 정렬을 해줘야하는 코드를 포함해야함

PriorityQueue 사용 코드

public class Main {
    public static int[] main(String[] args) {
        int k = 3;
        int[] score = {10, 100, 20, 150, 1, 100, 200};

        int[] answer = new int[score.length];

        PriorityQueue<Integer> scoreQueue = new PriorityQueue<>();  // PriorityQueue로 바꿈
        for (int i = 0; i < score.length; i++) {
            scoreQueue.offer(score[i]);
            if (scoreQueue.size() > k) {
                scoreQueue.poll();
                answer[i] = scoreQueue.peek();
            } else {
                answer[i] = scoreQueue.peek();
            }
        }
        return answer;
    }
}

 

• 표면적으로 코드 상으로는 제거하거나 재정렬을 하는 구조가 필요하지 않게 됨
  • 효율적으로 간략하게 처리 가능

ArrayList와 시간 복잡도 비교

• ArrayList일 경우 remove() 메서드 일경우, 맨 앞의 값 =최솟값을 삭재한다면, 모든 데이터를 앞 인덱스로 하나씩 당겨야 하기 때문에 O(N)의 시간복잡도
• PriorityQueue일 경우 heap 사용하기 때문에, 정렬, 삭제 관련하여 한번에 처리하는 것과 유사한 O(logN)의 시간 복잡도

-> 효율적인 코드와 연산처리

 

 

 

---

내일 부터는 Team Project가 시작이 될 것이기 때문에 피드백을 마친후 내일 부터는 팀 프로젝트가 진행할 수 있도록