[문제 풀이] 백준 1092번 배 JAVA

문제

 

  문제접근 방법   

해당 문제는 항구에서 화물을 배에 실어야하는 상황에서 화물을 옮길수 있는 크레인의 수 ,배의 옮겨야하는 화물의 개수가 주어졌을때 모든 박스를 배로 옮기는데 소요되는 시간의 최솟값을 구하는 프로그램을 작성하는 문제이다.

여기서 크레인은 한번에 옮길 수 있는 화물의 무게가 각각 정해져있다. 

처음에 문제를 듣고 탐색을 하기는 해야겠는데 범위가 애매하고 최솟값을 구한다기에 혹시 bfs로 문제를 풀어야하나?

라는 생각도 있었지만 도저히 아닌것같아서 자료구조의 Queue를 활용하여 코드를 접근하기로 하였다. 

전체적인 흐름은 다음과 같다. Queue를 통해서 크레인과 박스의 값을 받고 정렬한다. 그러면 가장 큰무게의 상자를 가장 많은 무게를 옮길 수 있는 크레인이 옮기게된다. 처음에만 크레인이 들수 있는 무게보다 상자의 무게가 무겁지 않다면 비교로 카운트가 가능하다. 그래서 앞서 말했던 경우는 -1을 출력하게하고 나머지는 비교하고 옮길 수 있으면 poll해서 상자 없애고 크레인은 다시 뒤로 가서 줄서고 이런 식의 흐름으로 코드를 구현하려하였다.

 

< 초기 코드  >

import java.util.*;

public class Main{
    public static void main(String args[]){
        Scanner s=new Scanner(System.in);
        PriorityQueue<Integer> crane=new LinkedList<>(Collections.reverseOrder());
        PriorityQueue<Integer> box=new LinkedList<>();
        Queue<Integer> crane2=new LinkedList<>();
        Queue<Integer> box2=new LinkedList<>();
        
        
        int cnt=0;
        int n=s.nextInt();
        for(int i=0;i<n;i++){
            crane.add(s.nextInt());
        }
        
        int m=s.nextInt();
        for(int i=0;i<m;i++){
            box.add(s.nextInt());
        }
        int breakCnt=0;
        while(breakCnt!=n||!box.isEmpty()){
            int craneN=crane.peek();
            int boxN=box.peek();
            
            if(craneN>=boxN){
                crane2.add(crane.poll());
                box.poll();
                breakCnt=0;
            }
            else{
                box2.add(box.poll());
                breakCnt++;
            }
            
            if(crane.isEmpty()){
                cnt++;
                for(int i=0;i<crane2.size();i++){
                    crane.add(crane2.poll());
                }
            }
            
            if(box.isEmpty()&&!box2.isEmpty()){
                for(int i=0;i<box2.size();i++){
                    box.add(box2.poll());
                }
            }
            
        }
        if(breakCnt==n){System.out.print(-1);}
        System.out.print(cnt);
        
        
    }
}

아이디어를 생각하고 초기 코드이다. 오래만의 자료구조 사용으로 미흡한 부분이 존재했지만 아이디어 자체는 나쁘지 않다고 생각했다. 위에서도 언급했지만 Queue에 박스,크레인의 값을 넣고 정렬해준다. 여기서 정렬을 위해 PriorityQueue를 활용하였다.

하지만 해당 코드에는 여러 문제가 존재했다. crane.peek()나 bok.peek()를 할때 큐가 비어있는지 별도로 확인하지 않아 

문제가 발생하기도하고 처음에는 -1처리 부분을 따로 빼야겠다고 생각한 부분을 코드를 작성하면서 의식의 흐름대로 합쳐버린 부분도 문제가 발생했다. 이런 전체적인 부분을 수정한 코드는 다음과 같다.

< 수정 코드 >

import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner s=new Scanner(System.in);
        PriorityQueue<Integer> crane=new PriorityQueue<>(Collections.reverseOrder());
        PriorityQueue<Integer> box=new PriorityQueue<>(Collections.reverseOrder());
        Queue<Integer> crane2=new LinkedList<>();
        Queue<Integer> box2=new LinkedList<>();

        int n=s.nextInt();
        for(int i=0;i<n;i++) crane.add(s.nextInt());

        int m=s.nextInt();
        for(int i=0;i<m;i++) box.add(s.nextInt());

        if(!crane.isEmpty() && !box.isEmpty() && box.peek()>crane.peek()){
            System.out.print(-1);
            return;
        }

        int cnt=0;
        while(!box.isEmpty()){
            int moved=0;
            while(!crane.isEmpty()){
                int c=crane.poll();
                while(!box.isEmpty() && box.peek()>c) box2.add(box.poll());
                if(!box.isEmpty()){
                    box.poll();
                    moved++;
                }
                crane2.add(c);
            }
            while(!crane2.isEmpty()) crane.add(crane2.poll());
            while(!box2.isEmpty()) box.add(box2.poll());
            if(moved==0){
                System.out.print(-1);
                return;
            }
            cnt++;
        }
        System.out.print(cnt);
    }
}

여러 부분을 수정해주었다. 먼저 -1이 되는 경우를 위에 한번 빼주어서 불필요한 반복을 최소화해주는 방향으로 구현하였고

가독성을 높이기위해 노력하였다. 하지만 결론적으로 해당 코드는  모든 예제의 값이 제대로 나오지만 메모리 초과를 해결하지 못했다. 그래서 어떤 알고리즘을 사용해야하는지 문제 아래의 알고리즘 칸을 확인한 후 다시 접근하기로 하였다.

 

< 최종 코드 >

import java.util.*;

public class Main{
    public static void main(String args[]){
        Scanner s=new Scanner(System.in);
        int day=0;
        
        int n=s.nextInt();
        Integer crane[]=new Integer[n];
        boolean visited[]=new boolean[n];
        for(int i=0;i<n;i++){
            crane[i]=s.nextInt();
        }
        
        int m=s.nextInt();
        List<Integer> box=new ArrayList<>();
        
        for(int i=0;i<m;i++){
            box.add(s.nextInt());
        }
        
        Arrays.sort(crane,Collections.reverseOrder());
        Collections.sort(box, Collections.reverseOrder());
        
        if(crane[0]<box.get(0)){System.out.print(-1);return;}
        
        while(!box.isEmpty()){
            int move=0;
            for(int i=0;i<n;){
                if(box.get(move)<=crane[i]){
                    i++;
                    box.remove(move);
                    move=0;
                }
                else{
                    move++;
                }
                if(move>=box.size())break;
            }
            day++;
        }
        System.out.print(day);

    }
}

본인은 처음 해당 문제가 그리디 문제인지 모르고 풀었다. 하지만 그리디라는 것을 깨닫고 아직 그리디를 잘모르는것 같아

해당 문제를 풀기전에 다른 그리디 문제로 그리디에 대해서 상기시키는 시간을 가졌다.

이후 위와 같이 코드를 작성하였다. 코드의 큰흐름은 크레인과 박스를 정렬하고 비교하는 과정에서 옮겼으면 박스 리스트에서 삭제 아니면 인덱스를 증가시켜서 옮길 수 있는 박스를 찾는다. 이를 크레인 수만큼 반복하고 과정이 끝날때마다 day를 증가 시켜준다.

여기서 핵심은 본 코드처럼 구성시 if(move>=box.size())break; 해당 코드처럼 빠져나올수 있는 코드가 필요하다.

예를 들어 크레인은 9 5  2 인데 9 5 4이렇게 옮겨야한다면 마지막 2크레인에서 계속 반복하다가 리스트의 범위를 넘어

에러가 발생하게 될 것이다. 그래서 move의 값이 리스트 사이즈보다 커지면 반복문을 빠져나가 다음 반복을 시작하게 하는것이다.

  마무리  

이전에 문제같은 경우 알고리즘의 카테고리를 정해두고 문제를 풀어 어려운 문제도 어렵지 않게 접근이 가능했지만

카테고리를 보지 않고 랜덤으로 문제를 풀게되니 접근부터가 문제였다. 나름 많은 문제를 풀어보았다고 생각했지만

아직 부족한 부분을 많이 느끼게 되는 문제였다.

또 처음에는 그리디라는 것을 확신하지 못하고 문제를 풀이하였지만 그리디라는 것을 확신하고 문제를 풀이하니

방향성이 보여서 좋았다.

  추가 코드 분석 및 풀이  

해당 문제는 문제의 범위가 본 코드와 맞아서 가능했지만 범위가 커진다면 위의 풀이는 시간복잡도가 좋은 코드는 아니라서 

풀이하지 못할 수도 있다. 이를 해결하기 위해서 검색해본 결과 TreeMap을 활용하면 시간초과의 위험성을 최소화시킬 수 있는 것을 확인 아래와 같이 풀이하였다.

 

< 추가 코드 ver TreeMap >

- 추후 업데이트 예정

 

 참고 자료 

• TreeMap