Java 프로그래머스 구명보트

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

프로그래머스

문제 분류 : 코딩테스트 연습 > 탐욕법(Greedy) > 구명보트

난이도 : 2

 

시간 초과 코드1

효율성 테스트 2개 틀렸다. -> 92.6 / 100

import java.util.*;
class Solution {
    public int solution(int[] people, int limit) {
        int answer = 0;
        PriorityQueue<Integer> pq = new PriorityQueue<>((o1,o2)-> -(o1-o2));
        for(int target : people) pq.add(target);
        PriorityQueue<Integer> pq2 = new PriorityQueue<>();
        while(!pq.isEmpty()){
            int cur = pq.poll();
            if(!pq2.isEmpty() && pq2.peek() + cur <= limit){
                pq2.poll();
                answer++;
                continue;
            }
            pq2.add(cur);
        }
        return answer + pq2.size();
    }
}

우선순위 큐는 삽입 삭제 연산이 O(logN)이다. 

매번 삽입하는데 O(logN)이 걸리니 효율성 테스트에서 틀린다.

우선순위 큐 대신 ArrayList로 바꾸고 값을 다 넣고 딱 1번만 정렬 해주면 우선순위 큐에 넣은 효과와 동일!

 

시간 초과 코드2

효율성 테스트 1개 틀렸다. -> 96.3 / 100

import java.util.*;
class Solution {
    public int solution(int[] people, int limit) {
        int answer = 0;
        ArrayList<Integer> list = new ArrayList<>();
        for(int target : people) list.add(target);
        Collections.sort(list, Collections.reverseOrder());
        PriorityQueue<Integer> pq2 = new PriorityQueue<>();
        for(int cur : list){
            if(!pq2.isEmpty() && pq2.peek() + cur <= limit){
                pq2.poll();
                answer++;
                continue;
            }
            pq2.add(cur);
        }
        return answer + pq2.size();
    }
}

 

문제점을 찾았다. 어차피 크기가 큰 순서대로 정렬을 하니까 스택으로 쌓아도 스택의 peek는 스택에서 가장 작은 값이다 즉 우선순위 큐를 사용하지 않아도 된다..

우선순위큐와 다르게 스택은 삽입 삭제 검색 모두 O(1)이다. 수정하면 이제 충분하게 통과가 예상된다.

 

시간 초과 코드3

효율성 테스트 3개 틀렸다. -> 88.9 / 100

import java.util.*;
class Solution {
    public int solution(int[] people, int limit) {
        int answer = 0;
        ArrayList<Integer> list = new ArrayList<>();
        for(int target : people) list.add(target);
        Collections.sort(list, Collections.reverseOrder());
        Stack<Integer> pq2 = new Stack<>();
        for(int cur : list){
            if(!pq2.isEmpty() && pq2.peek() + cur <= limit){
                pq2.pop();
                answer++;
                continue;
            }
            pq2.push(cur);
        }
        return answer + pq2.size();
    }
}

세상에 이게 무슨일이지... 왜 스택이 더 느릴까.. 

 

웃긴게 같은 코드여도 정답점수가 다르다 

스택 이름만 pq2 -> stack 으로 바꿔도 

효율성 테스트 1개 빼고 다 통과한다. 

 

정답 코드

덱을 활용해서 풀었다. 흠..

import java.util.*;
class Solution {
    public int solution(int[] people, int limit) {
        int answer = 0;
        Arrays.sort(people);
        Deque<Integer> dq = new LinkedList<>();
        for(int target : people) dq.addLast(target);
        while(!dq.isEmpty()){
            if(dq.size() >= 2 && dq.peekFirst() + dq.peekLast() <= limit){
                answer++;
                dq.pollFirst();
                dq.pollLast();
            }
            else if(dq.size() >= 2 && dq.peekFirst() + dq.peekLast() > limit){
                answer++;
                dq.pollLast();
            }
            else{
                answer++;
                dq.poll();
            }
        }
        return answer;
    }   
}