99클럽 코테 스터디 5일차 TIL - Heap

오늘의 학습 키워드

우선순위 큐

 

---

알고리즘 문제

• 프로그래머스 Level 2 - 더 맵게
• https://school.programmers.co.kr/learn/courses/30/lessons/42626

프로그래머스

---

공부한 내용

LinkedList와 ArrayList 의 시간복잡도 차이

 

PriorityQueue(우선순위 큐)

• Queue는 FIFO로 선입선출. 즉 먼저 들어간 놈이 먼저 나오는 구조였다.
• Queue 자료구조와 차이점은 들어가는 순서와 상관없이 우선순위가 높은 데이터가 먼저 나가는 자료구조라는 것.
• PriorityQueue는 힙 자료구조를 통해 구현될 수 있다.
• PriorityQueue 특징
  • 높은 우선순위의 요소를 먼저 꺼내서 처리하는 자료구조
  • 내부 구조는 힙으로 구성된 이진트리 구조
  • 시간복잡도는 O(nlogn)
• Java에서 PriorityQueue 사용방법

import java.util.*;

//Min Heap	// 우선순위: 낮은 숫자
PriorityQueue<Integer> pq1 = new PriorityQueue<>();
//Max Heap	// 우선순위: 높은 숫자
PriorityQueue<Integer> pq2 = new PriorityQueue<>(Collections.reverseOrder());

int a = 10;
pq1.add(a);		//추가 //반환 boolean(true) //overflow 시 IllegalstateException
pq1.offer(a);	//추가 //반환 boolean(true/false)
pq1.peek();		//삭제없이 우선순위 값 조회 //Queue 비어있으면 null return
pq1.poll();		//우선순위 값 조회 및 삭제  //Queue 비어있으면 null return
pq1.contains(Object); //현재 찾고자하는 값이 큐에 있으면 true, 없으면 false 반환
pq1.isEmpty(); 	//큐가 비어있으면 true, 아니면 false 반환
pq1.clear();	//큐 비우기

---

오늘의 회고

처음 시도

• 정확성 테스트는 통과했지만.. 효율성 테스트는 모두 실패했다.
• 왜? => 반복문을 돌면서 Collections.sort()로 정렬을 반복한 게 원인으로 보인다.

해결

• 우선순위 큐로 효율성을 해결해야 했다!

---

문제 풀이

• 정확도는 성공
• 효율성은 실패..

import java.util.*;

class Solution {
    public int solution(int[] scoville, int K) {
        int answer = 0;
        
        List<Integer> list = new LinkedList<>();
        for (int n : scoville) {
            list.add(n);
        }
        
        int mixed = 0;
        while (true) {
        	//음식을 섞어서 만들어서 맨 뒤에 add하기 때문에 매번 정렬
            Collections.sort(list);
            //앞에 정렬을 이미 했기 때문에 0번 인덱스 스코빌 지수가 K 이상이면 리턴!
            if (list.get(0) >= K) break;		// Early Return 조건.
            //위에서 못 빠져나갔고, 음식이 1개라면 못 섞는다 => K 이상 불가로 -1 리턴!
            if (list.size() == 1) return -1;	// Early Return 조건.
            
            //섞섞
            mixed = list.get(0) + list.get(1)*2;
            //마지막 섞섞 실패 => K 이상 불가로 -1 리턴!
            if (mixed < K && list.size() == 2) return -1;	// Early Return 조건.
            //위에서 Early Return에 안걸렸으면 음식 빼서 섞고 추가한다.
            list.remove(0);
            list.remove(0);
            list.add(mixed);
            answer++;
        }
        
        return answer;
    }
}

 

다른 풀이(PriorityQueue 사용)

• 프로세스는 위에 먼저 풀었던 것과 거의 비슷하다
• 대신 정렬을 할 필요가 없이 PriorityQueue가 우선순위로 값을 반환해주기 때문에 peek()로 대신했다.
• peek()가 K보다 같거나 크면 바로 리턴하도록 했다.
• 만약에 여기에 안걸리고 큐 크기가 1이라면 K 이상이 될 수 없어서 -1을 리턴한다.

import java.util.*;

class Solution {
    public int solution(int[] scoville, int K) {
        int answer = 0;
        
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for (int s : scoville) {
            pq.offer(s);
        }
        
        int mix = 0;
        int first = 0;
        int second = 0;
        while (pq.peek() < K) {            
            first = pq.poll();
            second = pq.poll();
            mix = first + second*2;
            pq.offer(mix);
            answer++;
            
            if (pq.peek() >= K) return answer;
            if (pq.size() == 1) return -1;
        }
        
        return answer;
    }
}