[코테/JAVA] 힙(Heap) : 더 맵게

2021.11.27

73번째 포스팅

 

입사 265일차.

코테 문제풀이 8주차 1번 문제

 

 

0. 문제

  ① 힙(Heap) : 더 맵게

  ② 설명

문제설명 매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같이 특별한 방법으로 섞어 새로운 음식을 만듭니다.   섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2) Leo는 모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복하여 섞습니다. Leo가 가진 음식의 스코빌 지수를 담은 배열 scoville과 원하는 스코빌 지수 K가 주어질 때, 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수를 return 하도록 solution 함수를 작성해주세요. 제한 사항 scoville의 길이는 2 이상 1,000,000 이하입니다. K는 0 이상 1,000,000,000 이하입니다. scoville의 원소는 각각 0 이상 1,000,000 이하입니다. 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우에는 -1을 return 합니다.

  ③ 링크

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

코딩테스트 연습 - 더 맵게

 

 

1. 접근방법

  생각해낸 방법은 2가지

  ① ArrayList<>를 사용

  ② LinkedList<>를 사용(Queue)

 

 

2. 풀이

  ① 접근방법 : ①

  ② 풀이

import java.util.*;
 
class Solution {
    /*
    * 시작시간 : 21:04
    * 종료시간 : 21:30
    */
    public int solution(int[] scoville, int K) {
        int answer = combineScovilleCnt(scoville, K);
        return answer;
    }
    
    public int combineScovilleCnt(int[] scoville, int K) {
        
        // 1. 오름차순으로 정렬
        Arrays.sort(scoville);
        List<Integer> list = new ArrayList<>();
        
        // 2. LinkedList에 배열을 담음
        for (int i = 0; i < scoville.length; i++) {
            list.add(scoville[i]);
        }
        
        // 3. 섞은 횟수 
        int cnt = 0;
        while(list.size() > 1) {
 
            // 4. 오름차순으로 정렬
            Collections.sort(list);
 
            // 5. 스코빌지수 계산
            List<Integer> foodList = combineScovilleLv(list);
 
            // 6. K미만의 스코빌지수가 있는지 확인
            int scovilleLvChck = 0;
            for (int i = 0; i < foodList.size(); i++) {
                if (foodList.get(i) < K) scovilleLvChck++;
            }
 
            // 7. 섞은횟수 더하기
            cnt++;
            list = foodList;
 
            if (scovilleLvChck == 0) break;
        }
 
        // 8. 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우에는 -1을 리턴
        int answer = cnt;
        if (list.size() == 1 && list.get(0) < K) answer = -1;
        return answer;
    }
 
    public List<Integer> combineScovilleLv(List<Integer> list) {
        int scovilleLv = 0;
        scovilleLv = list.get(0) + (list.get(1) * 2);
        
        List<Integer> foodList = new ArrayList<>();
        foodList.add(scovilleLv);
        
        for (int i = 2; i < list.size(); i++) {
            foodList.add(list.get(i));
        }
        
        return foodList;
    }
}

 

 

  ① 접근방법 : ②

  ② 풀이

import java.util.*;
 
class Solution {
    /*
    * 시작시간 : 21:04
    * 종료시간 : 21:30
    */
    public int solution(int[] scoville, int K) {
        int answer = combineScovilleCnt(scoville, K);
        return answer;
    }
    
    public int combineScovilleCnt(int[] scoville, int K) {
        
        // 1. 우선순위 큐 선언
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        
        // 2. 스코빌지수를 오름차순으로 add
        for (int i = 0; i < scoville.length; i++) {
            queue.offer(scoville[i]);
        }
 
        // 3. index(0) = 제일 작은 수가 K보다 커질때까지 반복
        int cnt = 0;
        while(queue.peek() < K) {
 
            // 4. 큐의 사이즈가 2보다 작아지면 더이상 섞을 수 없음
            if (queue.size() < 2) { 
                cnt = -1;
                break;
            }
            
            int num1 = queue.poll();
            int num2 = queue.poll();
            
            // 5. 스코빌지수 ㄱㅖ산
            int scovilleLv = combineScovilleLv(num1, num2);
            queue.offer(scovilleLv);
            cnt++;
        }
 
        return cnt;
    }
 
    
    public int combineScovilleLv(int num1, int num2) {
        int scovilleLv = 0;
        scovilleLv = num1 + (num2 * 2);
 
        return scovilleLv;
    }
}

 

 

3. 결과

 

 

4. 주의사항

  ① ArrayList로 풀 경우, 효율성 테스트를 통과할 수 없다.

  ② 이중반복문을 사용하면 안된다.