[고득점kit][힙][lv.2] 더 맵게 - 자바(Java)

 

프로그래머스 > 코딩테스트 연습 > 코딩테스트 고득점 Kit > 힙 > 더 맵게

 

문제 링크

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

 

 

 

---

 

문제

 

✅ 풀이 과정

0.  자료구조 / 알고리즘 선택

우선순위큐

 

이문제에서 링크드 리스트를 사용하면 효율성테스트에서 실패한다.

--- 링크드 리스트로 구현하고 시간을 비교해봐도 재밌을 것 같다. 나중에 해봐야지

 

 

1.  수도코드/ 알고리즘 생각

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

scoville	K	return
[1, 2, 3, 9, 10, 12]	7	2

입출력 예 설명

1. 스코빌 지수가 1인 음식과 2인 음식을 섞으면 음식의 스코빌 지수가 아래와 같이 됩니다.
   새로운 음식의 스코빌 지수 = 1 + (2 * 2) = 5
   가진 음식의 스코빌 지수 = [5, 3, 9, 10, 12]
2. 스코빌 지수가 3인 음식과 5인 음식을 섞으면 음식의 스코빌 지수가 아래와 같이 됩니다.
   새로운 음식의 스코빌 지수 = 3 + (5 * 2) = 13
   가진 음식의 스코빌 지수 = [13, 9, 10, 12]

요구사항:  모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수를 return 해야함.

 

 

 

1) Int형 우선순위 큐를 사용한다.

2) 가장 top에 있는 데이터가 k보다 작으면 반복한다.
top의 데이터는 가장 맵지 않은 음식이므로  만약 해당 값이 k 보다 클 경우, 모든 음식이 k보다 큰 것임

3) 만약 데이터가 2보다 작아졌는데 반복문을 타고 있으면 1개밖에 없는거므로 모든 음식의 스코빌 지수를 K이상으로 만들 수 없는것이다 -- -1을 리턴한다.

 

4) 큐에서 가장 맵지 않은 음식을 뺀다 (poll) 다음 음식도 뺀다(poll)

5) 두 음식이 섞인 스코빌 지수를 계산 해준다.

6) 계산된 값을 큐에 삽입한다.

7) 2-6의 반복 

 

 

 

2. 복잡도 고려

• scoville의 길이는 2 이상 1,000,000 이하입니다.
• K는 0 이상 1,000,000,000 이하입니다.
• scoville의 원소는 각각 0 이상 1,000,000 이하입니다.
• 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우에는 -1을 return 합니다.

 

 

 

시간복잡도
offer(입력)   : O(log n)
peek(get)     : O(1)
poll(반환)    : O(log n)
size          : O(1)
natural order : JVM에서 제공하는 일반적인거와 다를수 있음 순서 ex) 문자는 ASCII 순서로 정렬
java 1.5 에서 나옴
특징 : 일반적은 큐는 FIFO의 구조를 가지지만 자연 네추럴 오더에 따라 정렬
      - Null을 허용하지 않는다.

우선순위큐의 시간복잡도와 알고리즘을 고려하면 계산은

 

\-------🥹졸려서 계산이 잘 되고있는건지 모르겠다 오늘은 빨리자야지.. _-------읽지마시오

scoville의 길이 == 1,000,000 (백만개의 데이터)

K는 0 이상 1,000,000,000 이하

scoville의 원소는 각각 0 이상 1,000,000 이하

 

최악의 케이스는 k가 1,000,000,000 인데, 모든 scoville 데이터의 값이 1인경우.

계속 더하고 넣고의 반복...

 

백만개를 더하고 넣고 하다보면.. 결국 2개의 값을 빼고 연산하므로
100만번-1만큼 빠질것이고,

 

다시 큐에 해당 값을 넣는게 100만번-1 만큼 들어갈것이다.. ? 휴 피곤하다

 

 

 

✅ 내가 쓴 정답코드

PriorityQueue 를 사용했다.

 

자바의 우선순위큐는 그냥 생성하면 최소힙으로 만들어준다.

 

아래 메서드를 사용해서 구현만 하면 된다.

• peek() 맨앞에 값 보기
• poll() 맨앞 빼기
• add(), offer() 넣기

 

import java.util.PriorityQueue;

class Solution {
    public int solution(int[] scoville, int K) {
        Integer answer = 0;
        Integer one, two;
        PriorityQueue<Integer> queue = new PriorityQueue<Integer>();//큐 생성

        //할당
        for (int i = 0; i < scoville.length; i++) {
            queue.add(scoville[i]);
        }

        while(queue.peek() < K) {
            //int형 우선순위가 낮은 숫자 순
            if (queue.size() < 2) {
                return -1;
            }
            else {
                one = queue.poll();
                two = queue.poll();

                one += (two * 2);
                queue.offer(one);
                answer += 1;
            }
        }
        return answer;
    }
}

 

 

 

✅ 문제를 풀기 위해 새롭게 학습한 것

 

우선순위큐 (Priority Queue) 사용 방법

 

- 시간복잡도

시간복잡도
offer(입력)   : O(log n)
peek(get)     : O(1)
poll(반환)    : O(log n)
size          : O(1)
natural order : JVM에서 제공하는 일반적인거와 다를수 있음 순서 ex) 문자는 ASCII 순서로 정렬
java 1.5 에서 나옴
특징 : 일반적은 큐는 FIFO의 구조를 가지지만 자연 네추럴 오더에 따라 정렬
      - Null을 허용하지 않는다.

 

- 큐의 성질을 가졌으나, 각 데이터가 우선순위를 갖고 있어 우선순위가 높은 순서대로 나옴  (우선순위가 동일할 경우는 큐의 순서대로)

 

- 내부 요소는 힙으로 구성되어 이진트리의 구조로 이루어져 있다. 시간복잡도는 O(NLogN)

 

- Min Heap으로 데이터를 정렬하고 데이터를 출력한다

 

- 값 추가, 삭제 등은 연결 리스트 (LinkedList)와 동일

 

import java.util.PriorityQueue;
import java.util.Collections;

//낮은 숫자가 우선 순위인 int 형 우선순위 큐 선언
PriorityQueue<Integer> priorityQueueLowest = new PriorityQueue<>();

//높은 숫자가 우선 순위인 int 형 우선순위 큐 선언
PriorityQueue<Integer> priorityQueueHighest = new PriorityQueue<>(Collections.reverseOrder());

 

 

 

 

 

---

references

프로그래머스 고득점키트

https://coding-factory.tistory.com/603

https://developer-c.tistory.com/83