JAVA 백준 1092 배 (그리디, 정렬) - 미완

 

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

 

---

문제

1. 첫째 줄에 N( 1 <= N <= 50 ) 입력.
2. 둘째 줄에 크레인 N개의 무게 제한 (1 <= 무게 제한 <= 1000000) 을 순서대로 입력.
3. 셋째 줄에 M( 1 <= M <= 10000 )
4. 넷째 줄에 박스 M개의 무게 (1 <= 무게 <= 1000000) 를 순서대로 입력.
5. 크레인 N개가 1분에 박스를 하나씩 옮길 수 있고 동시에 움직일 때 모든 박스를 배로 옮기는 데 드는 시간의 최솟값 출력.

---

 

초기 코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int time = 0, count = 0;

        int N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());

        int[] crane = new int[N];

        for (int i = 0; i < N; i++) {
            crane[i] = Integer.parseInt(st.nextToken());
        }

        int M = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());

        br.close();

        ArrayList<Integer> box = new ArrayList<>();

        for (int i = 0; i < M; i++) {
            box.add(Integer.parseInt(st.nextToken()));
        }

        Arrays.sort(crane);
        Collections.sort(box);

        if (crane[N - 1] < box.getLast()) {
            System.out.println("-1");
        } else {
            while (!box.isEmpty()) {
                time++;
                if (crane[0] >= box.getFirst()) {
                    box.removeFirst();
                    count++;
                }
                if (!box.isEmpty() && crane[N - 1] >= box.getLast()) {
                    box.removeLast();
                    count++;
                }
                if (N > 2) {
                    for (int i = N - 2; i > 0; i--) {
                        for (int j = M - count; j >= 0; j--) {
                            if (!box.isEmpty() && crane[i] >= box.getLast()) {
                                box.removeLast();
                                count++;
                                break;
                            }
                        }
                    }
                }
            }
        }

        System.out.println(time);
    }
}

 

자바 11에서는 getLast랑 getFirst 같은 메소드가 없어서 컴파일 에러가 났다.

 

수정 코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int time = 0, count = 0;

        int N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());

        int[] crane = new int[N];

        for (int i = 0; i < N; i++) {
            crane[i] = Integer.parseInt(st.nextToken());
        }

        int M = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());

        br.close();

        ArrayList<Integer> box = new ArrayList<>();

        for (int i = 0; i < M; i++) {
            box.add(Integer.parseInt(st.nextToken()));
        }

        Arrays.sort(crane);
        Collections.sort(box);

        if (crane[N - 1] < box.get(box.size()-1)) {
            System.out.println("-1");
        } else {
            while (!box.isEmpty()) {
                time++;
                if (crane[0] >= box.get(0)) {
                    box.remove(0);
                    count++;
                }
                if (!box.isEmpty() && crane[N - 1] >= box.get(box.size()-1)) {
                    box.remove(box.size()-1);
                    count++;
                }
                if (N > 2) {
                    for (int i = N - 2; i > 0; i--) {
                        for (int j = M - count; j >= 0; j--) {
                            if (!box.isEmpty() && crane[i] >= box.get(box.size()-1)) {
                                box.remove(box.size()-1);
                                count++;
                                break;
                            }
                        }
                    }
                }
            }
        }

        System.out.println(time);
    }
}

 

예제는 다 맞았는데 틀렸다고 나와서 다시 수정해야 됨...

근데 뭐가 틀렸는지 모르겠습니다

 

https://www.acmicpc.net/board/view/122007

어떤 분이 테스트 케이스 모아놓으셨네요 감사합니다...

 

테스트 케이스도 모두 맞은 코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int time = 0, count = 0, first=0;

        int N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());

        int[] crane = new int[N];

        for (int i = 0; i < N; i++) {
            crane[i] = Integer.parseInt(st.nextToken());
        }

        int M = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());

        br.close();

        ArrayList<Integer> box = new ArrayList<>();

        for (int i = 0; i < M; i++) {
            box.add(Integer.parseInt(st.nextToken()));
        }

        Arrays.sort(crane);
        Collections.sort(box);


        if (crane[0] < box.get(0)) {
            for (int i = 1; i < N; i++) {
                if(crane[i] >= box.get(0)){
                    first = i;
                    break;
                }
            }
        }

        if (crane[N - 1] < box.get(box.size() - 1)) {
            System.out.println("-1");
        } else {
            while (!box.isEmpty()) {
                time++;
                if (crane[first] >= box.get(0)) {
                    box.remove(0);
                    count++;
                }
                if (!box.isEmpty() && crane[N - 1] >= box.get(box.size() - 1)) {
                    box.remove(box.size() - 1);
                    count++;
                }
                if (N > 2) {
                    for (int i = N - 2; i > first; i--) {
                        for (int j = M - count; j > 0; j--) {
                            if (!box.isEmpty() && crane[i] >= box.get(j-1)) {
                                box.remove(j-1);
                                count++;
                                break;
                            }
                        }
                    }
                }
            }
        }
        if (count != 0) {
            System.out.println(time);
        }
    }
}

 

더 이상 고칠 부분도 모르겠고 시간초과 나는 건 아는데 그것도 못 보니 일단 이대로 놔두겠습니다