[Java] 프로그래머스 - 더 맵게 (2단계)

코딩 테스트 풀이 체크리스트
2시간 내에 풀었는가?	O
본인의 실력으로 풀었는가?	X

 

코딩테스트 연습 - 더 맵게

 

 

 

 

 

import java.util.*;
class Solution {
    
    ArrayList<Integer> heap = new ArrayList<>();
    
    public int solution(int[] scoville, int K) {
        int answer = 0;
        
        heap.add(0);
        for (int num : scoville) {
            func(num);
        }
        
        while (heap.size() > 2) {
            
            if (heap.get(1) >= K) break;
            
            answer++;
            
            int a = delete();
            int b = delete();
            
            func(a + (b * 2));
        }

        if (heap.get(1) < K) return -1;
        
        return answer;
    }
    
    public int delete() {
        
        if (heap.size() - 1 < 1) return 0;
        
        int result = heap.get(1);
        
        heap.set(1, heap.get(heap.size()-1));
        heap.remove(heap.size()-1);
        
        int parent = 1;
        
        while (parent * 2 < heap.size()) {
            int child = parent * 2;
            
            if (child + 1 < heap.size() && heap.get(child) > heap.get(child+1)) {
                child = child + 1;
            }
            
            if (heap.get(parent) >= heap.get(child)) {
                int temp = heap.get(parent);
                heap.set(parent, heap.get(child));
                heap.set(child, temp);
            
                parent = child;
            } else {
                break;
            }
        }
        
        return result;
    }
    
    public void func(int num) {
        heap.add(num);
        
        int p = heap.size() - 1;
        
        while (p > 1 && heap.get(p / 2) > heap.get(p)) {
            int temp = heap.get(p / 2);
            heap.set(p / 2, heap.get(p));
            heap.set(p, temp);
            p /= 2;
        }
    }
}

 

정확성 테스트

테스트 1 〉	통과 (0.06ms, 87.8MB)
테스트 2 〉	통과 (0.07ms, 74.8MB)
테스트 3 〉	통과 (0.08ms, 76.5MB)
테스트 4 〉	통과 (0.09ms, 71.9MB)
테스트 5 〉	통과 (0.09ms, 73.8MB)
테스트 6 〉	통과 (4.46ms, 77.5MB)
테스트 7 〉	통과 (3.68ms, 83.4MB)
테스트 8 〉	통과 (0.69ms, 67.7MB)
테스트 9 〉	통과 (0.91ms, 76.9MB)
테스트 10 〉	통과 (3.55ms, 81.8MB)
테스트 11 〉	통과 (2.58ms, 75.8MB)
테스트 12 〉	통과 (5.71ms, 79.9MB)
테스트 13 〉	통과 (3.09ms, 76.3MB)
테스트 14 〉	통과 (0.22ms, 77.8MB)
테스트 15 〉	통과 (4.32ms, 77.2MB)
테스트 16 〉	통과 (0.05ms, 76.1MB)

 

효율성 테스트

테스트 1 〉	통과 (222.08ms, 83.4MB)
테스트 2 〉	통과 (467.93ms, 142MB)
테스트 3 〉	통과 (2380.71ms, 267MB)
테스트 4 〉	통과 (176.82ms, 74.7MB)
테스트 5 〉	통과 (2409.68ms, 300MB)

 

 

 

 

 

최소 힙 정렬을 이용해서 구하는건데, 일단 내가 보고 참고한 것은 최대 힙에 대한 설명이었다.

 

 

 

 

 

 

 

 

 

 

방식은 비슷해서.. 저거 보고 참고하면서 최소 힙을 구현했는데,

최소 힙 구현만 했다면 나머지는 간단해서 코드 보면 이해가 바로 갈 것이다.