99클럽 코테 스터디 5일차 TIL 더 맵게

https://school.programmers.co.kr/learn/courses/30/lessons/42626

프로그래머스

 

 

 

1. 문제 및 접근법

 

모든 음식을 k 수만큼 만들고 싶어한다. (스코빌 지수를 k만큼)

그래서 섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2)로 만든다

다 넘을 때 까지 반복하는데 최소로 반복하고 싶음

 

 

문제 풀이

우선 배열 정렬 후 작은 수를 반복해서 정렬로 풀려고 했는데

N^2로 최소 값 찾고 맞는 수로 정렬하면 + n log n이라 시간 복잡도 pass.

문제 유형을 보니 heap이고 우선순위 큐를 위해 최소 힙과 최대 힙에 자세히 알아보고 최소 힙 구현하기

 

근데 젤낮은건 k가 안되고 두번째로 낮은건 k 이상이면 조합 가능한가 ? 일단 된다고 생각하고 짜자

 

 

 

2. 풀이법

 

 

minHeap

 

첫 째로 최소힙은 우선순위 큐를 그대로 사용하면 된다 !

 

나중에 실제 구현도 다시 하자

 

 

 

maxHeap

우선순위 큐를 comparator로

정렬을 해주는데,

Integer의 compare 값이 default 값으로 들어가게 되는데 이 값을 -로 바꿔주면 maxHeap이 된다.

 

++추가 (정렬 메서드 두개 compare , Comparator 링크 붙이기!) 

 

 

 

 

 

 

 

실제 풀이

private int solution(int[] scoville, int K) {

    PriorityQueue<Integer> minHeap = new PriorityQueue<>();

    for (int i = 0; i < scoville.length; i++) {
        minHeap.add(scoville[i]); // 따로 배열에 넣고 하나씩 돌려줬다. 다른 방법으로 더 편리하게 생각
    }
    int answer = 0;



    while (minHeap.peek() != null && minHeap.peek() < K) {
        // peek 했을 때 null 체크 해주기 

        if (minHeap.size() < 2) {
            return -1; // 결합할 충분한 요소가 없음
        } // size가 하나 남았다면 불가능하다는 것!

        int a = minHeap.poll();
        int b = minHeap.poll();

        minHeap.add(a + (b * 2));
        answer++;


    }

    return answer;

    }

 

 

while 문을 도는 동안 peek 하면 우선순위에 따라 제일 작은 값이 뽑히고 그 값이 k보다 작다면 

그 값 (제일 작은 값) 과 다음으로 작은 값을 뽑아 스코빌 지수로 만들어주고 횟수를 하나 세준다.

 

 

 

간단하지만, 글 이해를 잘못해서 b + (a *2)로 해서 계속 틀렸다 ㅠㅠ 잘 읽자 !

 

 

 

 

3. 느낀 점

 

 

프로그래머스에서 AI로 피드백해줬는데 너무 편하다 이러다가 나 취업 못하는 거 아닌가 몰라 ㅠㅠ

그렇다면 ! AI를 잘 활용할 수 있는 사람이 되자..

 

 

문제를 너무 대충 읽는다.. 자료구조에 대한 기본도 공부하자

 

우선순위 큐를 내 입맛대로 잘 활용하게 추가해보자

 

 

 

 

 

번외. PriortyQueue & Heap

 

우선순위 큐: 우선순위의 개념을 큐에 도입한 자료 구조
데이터들이 우선순위를 가지고 있고 우선순위가 높은 데이터가 먼저 나간다.

 

우선순위 큐의 이용 사례

 

 

 

• 시뮬레이션 시스템
• 네트워크 트래픽 제어
• 운영 체제에서의 작업 스케쥴링
  
  
  

수치 해석적인 계산우선순위 큐는 배열, 연결리스트, 힙 으로 구현이 가능하다. 이 중에서 힙(heap)으로 구현하는 것이 가장 효율적이다.

 

 

자료구조 ‘힙(heap)’이란?

 

완전 이진 트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조이다.

 

여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조이다.

힙은 일종의 반정렬 상태(느슨한 정렬 상태) 를 유지한다.

큰 값이 상위 레벨에 있고 작은 값이 하위 레벨에 있다는 정도

간단히 말하면 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰(작은) 이진 트리를 말한다.
https://gmlwjd9405.github.io/2018/05/10/data-structure-heap.html 

 

 

우선순위 큐 (Priority Queue):

• 우선순위 큐는 데이터를 저장할 때 우선순위에 따라 저장하고, 우선순위가 높은 데이터를 먼저 꺼내는 자료구조
• 주어진 데이터를 삽입할 때 우선순위에 따라 정렬하여 삽입하며, 가장 높은 우선순위를 가진 데이터를 먼저 꺼냄
• 일반적으로 우선순위 큐는 힙(Heap)이라는 자료구조를 기반으로 구현됨

힙 (Heap):

• 힙은 완전 이진 트리(Complete Binary Tree)의 일종으로, 부모 노드의 값이 자식 노드의 값보다 항상 크거나 작은 특성을 가짐
• 최소 힙(Min Heap): 부모 노드의 값이 항상 자식 노드의 값보다 작은 힙, 루트 노드가 최소값을 가짐
• 최대 힙(Max Heap): 부모 노드의 값이 항상 자식 노드의 값보다 큰 힙, 루트 노드가 최대값을 가짐
• 힙은 삽입, 삭제, 최솟값/최댓값 조회 등의 연산을 𝑂(log 𝑛)
  
  
  O(logn) 시간에 수행할 수 있는 효율적인 자료구조

힙은 보통 배열을 기반으로 구현되며, 부모와 자식 간의 관계를 유지하면서 데이터를 추가하거나 삭제하여 힙의 특성을 유지함

힙을 사용하여 우선순위 큐를 구현함

또 이진트리는 안되지만 힙은 중복을 허용한다~

 

 

https://gmlwjd9405.github.io/2018/05/10/data-structure-heap.html (이미지 출처)