백준(BOJ) 1092: 배

https://www.acmicpc.net/problem/1092

문제가 깔끔하지 않을수 있다. 여기서 깔끔하지 않다는 것은 어떠한 명확한 알고리즘을 묻는것도 아니고, 그 알고리즘을 감추어 놓은 것도 아니고, 알고리즘과 관련된 어떠한 참신한 생각을 떠올려야 풀리는 문제도 아닌 문제를 말한다. 하지만 이런 더러운 문제도 가치가 있다. 왜? 이러이러한 문제가 내가 알고있는 어떠한 해결법으로는 깔끔하게 풀리지 않는다는 것을 알려준다는 점에서 그러하다. 

나는 이문제가 "최소 회의실 개수" 문제와 같이 우선순위 큐를 이용하여 풀릴줄 알았다. 그래서 그렇게 접근해 보았지만 예제 테스트를 모두 통과했지만 결국 오답이 나왔다. 코드는 상당히 지저분했다. 즉, 최소 회의실 문제는 PriorityQueue에 넣는 것도 회의객체이고 그 객체를 큐에서 빼서 비교하는 대상도 회의 객체이다. 하지만 이 문제는 다르다. 우선순위 큐를 사용한다면 우선순위 큐에 들어가는 것은 크래인이고 큐에 있는 크래인과 비교되는 것은 화물의 무개이다. 그러한 점에서 우선순위큐로는 이 문제를 깔끔하게 풀수 없는거같다. 

아래는 우선순위큐를 이용한 오답코드이다. 예제는 모두 통과됨.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.lang.reflect.Array;
import java.util.*;

public class Testing3{
    public static void solution(int[]cranes, int[]boxes){
        int cn=cranes.length;
        int size=boxes.length;
        List<Integer>keeping=new LinkedList<>();
        PriorityQueue<Integer>pq=new PriorityQueue<>(Collections.reverseOrder());
        for(int i=0;i<cranes.length;i++)
            pq.add(cranes[i]);
        boxes=Arrays.stream(boxes).boxed().sorted(Collections.reverseOrder()).mapToInt(Integer::intValue).toArray();
        int answer=0;
        int i=0;
        while(i<size){
            while(!pq.isEmpty()){
                int crane=pq.peek();
//                System.out.println(i+"st crane: "+crane);
                if(crane>=boxes[i]){
//                    System.out.println("used crane: "+crane);
                    keeping.add(pq.poll());
                    ++i;
                    if(i>=size)
                        break;
                }
                else{
                    if(pq.size()==cn){
                        System.out.println(-1);
                        return;
                    }
                    while(keeping.size()>0){
                        pq.add(keeping.remove(0));
                    }
                    ++answer;
                }
            }
            for(int k=0;k<cranes.length;k++)
                pq.add(cranes[k]);
            ++answer;
        }
        System.out.println(answer);
    }
    public static void main(String[] args) throws Exception{
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        int crane=Integer.parseInt(br.readLine());
        int[]cranes= Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        int box=Integer.parseInt(br.readLine());
        int[]boxes= Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        solution(cranes, boxes);
    }
}

 

아래 코드에서 ArrayList를 LinkedList로 바꾸면 List에 있는 데이터를 삭제할때 더 빨라질수 있지 않을까 해서 바꾸었지만 결과적으로는 더 느려졌다. 나름 생각해 보면 값을 비교하기 위해 해당 인덱스로 바로 찾아가는 것이 ArrayList가 더 빠르기 때문인 것 같다. 

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Testing3{
    public static void solution(List<Integer>crane, List<Integer>box){
        int answer=0;
        int n=crane.size();
        while(!box.isEmpty()){
            int boxIdx=0, craneIdx=0;
            while(craneIdx<n){
                if(boxIdx== box.size())
                    break;
                else if(crane.get(craneIdx)>=box.get(boxIdx)){
                    box.remove(boxIdx);
                    ++craneIdx;
                }
                else
                    ++boxIdx;
            }
            ++answer;
        }
        System.out.println(answer);
    }
    public static void main(String[] args)throws  Exception{
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        int n=Integer.parseInt(br.readLine());
        List<Integer> crane=new ArrayList<>();
        StringTokenizer st=new StringTokenizer(br.readLine()," ");
        for(int i=0;i<n;i++)
            crane.add(Integer.parseInt(st.nextToken()));
        crane.sort(Collections.reverseOrder());

        int m=Integer.parseInt(br.readLine());
        st=new StringTokenizer(br.readLine());
        List<Integer>box=new ArrayList<>();
        for(int i=0;i<m;i++)
            box.add(Integer.parseInt(st.nextToken()));
        box.sort(Collections.reverseOrder());


        if(box.get(0)>crane.get(0)){
            System.out.println(-1);
            return;
        }

        solution(crane, box);
    }
}