[알고리즘] 프로그래머스 더 맵게 -힙(heap)-

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

프로그래머스

 

할거하고 자기전에 알고리즘 가볍게 생긴걸로 한문제 풀고 잘려했는데 틀렸네요 ㅋㅋ

테스트케이스는 다 통과하였는데 효율성테스트에서 다 시간초과가 떳습니다. 후

 

힙문제라 그런지 힙으로 풀어야하나봅니다. 힙(우선순위큐)는 애초에 들어갈 때 부터 정렬에 최적화 된 자료구조라 효율성이 리스트보다 당연히 좋습니다.

힙문제 같으면 꼭 힙 우선순위큐를 사용해서 풉시다..! 

틀린 후 바로 리스트를 큐로만 변경해줬더니 통과되었습니다. ㅎㅎ 

 

 

테스트케이스는 다 맞았으나 효율성에서 틀린 코드는 다음과 같습니다.

import java.util.ArrayList;
import java.util.Comparator;

class Solution {
    public static void main(String[] args) {
        Solution solution = new Solution();
        solution.solution(new int[]{1, 2, 3, 9, 10, 12}, 7);
    }

    public int solution(int[] scoville, int K) {
        int answer = 0;
        ArrayList<String> list = new ArrayList<>();
        for (int i : scoville) {
            list.add(String.valueOf(i));
        }
        if (list.size() == 1) {
            if (Integer.parseInt(list.get(0)) >= K) {
                return 0;
            } else {
                return -1;
            }
        }
        list.sort(new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                return Integer.parseInt(o1) - Integer.parseInt(o2);
            }
        });
        while (Integer.parseInt(list.get(0)) < K && list.size() >= 2) {
            String a = list.get(0);
            String b = list.get(1);
            int newScob = Integer.parseInt(a) + (Integer.parseInt(b) * 2);
            list.remove(a);
            list.remove(b);
            list.add(String.valueOf(newScob));
            list.sort(new Comparator<String>() {
                @Override
                public int compare(String o1, String o2) {
                    return Integer.parseInt(o1) - Integer.parseInt(o2);
                }
            });
            answer++;
        }
        if (Integer.parseInt(list.get(0)) < K) {
            return -1;
        }
        System.out.println(answer);
        return answer;
    }
}

 

 

 

 

우선순위큐로 바꾼 후 통과한 코드는 다음과 같습니다.

import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;

class Solution {
    public static void main(String[] args) {
        Solution solution = new Solution();
        solution.solution(new int[]{1, 2, 3, 9, 10, 12}, 7);
    }

    public int solution(int[] scoville, int K) {
        int answer = 0;
        Queue<Integer> queue = new PriorityQueue<>();
        for (int i : scoville) {
            queue.add(i);
        }
        if (queue.size() == 1) {
            if (queue.peek() >= K) {
                return 0;
            } else {
                return -1;
            }
        }
        while (queue.peek() < K && queue.size() >= 2) {
            int a = queue.poll();
            int b = queue.poll();
            int newScob = a +(b* 2);
            queue.add(newScob);
            answer++;
        }
        if (queue.peek() < K) {
            return -1;
        }
        System.out.println(answer);
        return answer;
    }
}

 

 

요즘 노는것도 있지만 알고리즘을 할 시간이 잘 안나네요... 빨리 시간내서 DFS, BFS, DP, 백트랙킹 문제 위주로 풀어야겠습니다. 

 

댓글과 공감은 큰 힘이됩니다. 감사합니다.!!