[자바] 1092 배

자바 / 골5 / 그리디 알고리즘

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

 

ㅜㅜ 첫 접근을 잘못해서 시간을 많이많이 쓰고 정말 힘두러따

계속 될 것 같은데... 하면서 계속 그냥... 그냥 안되는 코드를.. 점점 복잡하게 만들면서... 계쏙계쏙.... 멈추지 못하고... 계속 풀어따........... 그리디라는, 매 순간 최적의 해 라는 알고리즘 접근법에서는 이미 한참 벗어났는데도....ㅜㅜㅜㅜㅜㅜㅜㅜㅜ

중간에 한 번 친구의 도움으로... 하던 걸 멈추고 생각을 refresh하는 과정을 가졌다.. 근데 너무 늦게 가졌다 흑흑

arraylist라는 자료형도 자바에서는 처음 다뤄본 것 같다. 상자의 자료형을 처음에는 그냥 배열로 했다가 뭐였지? 뭐가 접근이 안돼서 아 그럼 우선순위 큐를 써볼까? < 절망의 시작.. 최근에 사용했던 우선순위 큐가 머리에 떠오른 게 문제였다. arraylist에 대해서는 생각도 못했다. 이론만 전공에서 배웠지 코딩에 사용해 본 적은 없었어서... 

그래도 어레이리스트에 대해 배웠으니 그래도... arrayList에 대해서는 추후 또 정리하도록 하겠다.

그리고 앞으로는 일정 시간이 넘어가면 하던 접근법에서 주기적으로 머리를 환기하는 시간을 가져야겠다는 교훈도..

여러모로 많이 헤멘 문제였다

 

그래서... 구글도 참고하고 얻은 최종 알고리즘

우선, 가장 무거운 상자를, 무게 제한이 가장 큰 크레인이 들 수 없다면 -1을 반환하고 종료하는 코드를 세웠다.

        if (crane.get(j) < box.get(i)) {
            System.out.println("-1");
            return ;
        }

 

그리고, 매 순간 최적의 해 - 각 크레인이 들 수 있는 가장 무거운 상자를 들고, 해당 상자를 arrayList에서 제거하는 방식으로 코드를 세웠다. 이렇게 쉬운 알고리즘을!!!!! (ㅜㅜ)

        while (!box.isEmpty()) {
            i = box.size() - 1;
            j = N - 1;
            
            while (j >= 0) { 
                if (i < 0) break;
                else if (crane.get(j) >= box.get(i)){
                    box.remove(i);
                    j--;
                    i--;
                }
                else {
                    i--;
                }
            }
            cnt++;
        }

 

다음은 전체 코드이다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.ArrayList;
import java.util.Collections;

public class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s;
        StringTokenizer st;
        int N, M, i, j, cnt = 0;
        ArrayList<Integer> crane = new ArrayList<>();
        ArrayList<Integer> box = new ArrayList<>();

        N = Integer.parseInt(br.readLine());
        s = br.readLine();
        st = new StringTokenizer(s);
        for(i = 0; i < N; i++) {
            crane.add(Integer.parseInt(st.nextToken()));
        }

        M = Integer.parseInt(br.readLine());
        s = br.readLine();
        st = new StringTokenizer(s);
        for(i = 0; i < M; i++) {
            box.add(Integer.parseInt((st.nextToken())));
        }

        Collections.sort(crane);
        Collections.sort(box);
        
        i = M - 1;
        j = N - 1;

        if (crane.get(j) < box.get(i)) {
            System.out.println("-1");
            return ;
        }
        
        while (!box.isEmpty()) {
            i = box.size() - 1;
            j = N - 1;
            
            while (j >= 0) { 
                if (i < 0) break;
                else if (crane.get(j) >= box.get(i)){
                    box.remove(i);
                    j--;
                    i--;
                }
                else {
                    i--;
                }
            }
            cnt++;
        }

        System.out.println(cnt);
    }
}