백준 30504번 : 세과영엔 슬픈 전설이 있어

1. 문제

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

 

문제

세종이는 영재에게 빌려준 돈을 현재까지도 받지 못했다. 세종이는 영재에게 돈을 갚으라고 여러 번 독촉했지만, 슬프게도 영재는 세종이의 말을 알아듣지 못하는 것 같다. 그래서 세종이는 영재에게 마지막 유예 기간 N$N$일을 주었다. 영재는 세종이가 준 N$N$일 동안 빌린 돈을 모두 갚아야 한다.

세종이와 영재에게는 특이한 규칙이 있다. 세종이는 i$i$일째 되는 날에 Ai$A_i$ 만큼 분노한다. 만약 i$i$일에 세종이가 Ai$A_i$원 이상의 돈을 받지 못한다면 세종이는 영재에게 분노를 표출하게 된다. 영재는 자신이 가진 돈을 N$N$개의 자루에 나누어 담아 세종이에게 하루에 한 자루씩 주려고 한다.

세종이가 받아야 하는 최소 금액과 영재가 나눠 담은 금액이 주어졌을 때, 영재가 세종이의 분노를 피해 빚을 갚는 방법을 찾는 프로그램을 작성하시오.

입력

첫째 줄에 유예 기간의 날짜 수 N$N$이 주어진다. (1≤N≤200000)$(1\leq N\leq 200\, 000)$ 

둘째 줄에 N$N$개의 양의 정수 A1$A_1$, A2$A_2$, ⋯$\cdots$, AN$A_N$이 공백으로 구분되어 주어진다. 이때 Ai$A_i$는 i$i$번째 날에 세종이가 받아야 하는 최소 금액이다. (1≤Ai≤108)$(1\le A_i\le 10^{8})$ 

셋째 줄에 N$N$개의 양의 정수 B1,B2,⋯,BN$B_1,B_2,\cdots ,B_N$이 공백으로 구분되어 주어진다. 이때 Bj$B_j$는 영재가 j$j$번째 자루에 담은 금액이다. (1≤Bj≤108)$(1\le B_j\le 10^{8})$ 

 ∑i=1NAi≤2×109;$\sum_{i=1}^{N}{A_i}\le 2\times 10^{9};$ ∑j=1NBj≤2×109$\sum_{j=1}^{N}{B_j}\le 2\times 10^{9}$ 이다.

출력

영재가 1$1$일부터 N$N$일까지 각 날마다 지불해야 하는 금액을 공백으로 구분해 출력한다.

만약 빚을 갚는 것이 불가능해 세종이가 분노를 표출하게 된 경우 대신 -1을 출력한다.

가능한 답이 여러 가지인 경우 그 중 아무거나 하나만 출력한다.

 

예제 입력 1 복사

5
1 2 3 4 5
7 3 2 5 4

 

예제 출력 1 복사

2 3 4 5 7

3 2 4 5 7, 2 4 3 5 7 등의 방법 역시 가능하다.

 

예제 입력 2 복사

3
1 3 10000
9999 9999 9999

 

예제 출력 2 복사

-1

2. 코드

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

public class Main {

    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringTokenizer st2 = new StringTokenizer(br.readLine());
        int[] A = new int[N];
        ArrayList<Integer> B = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            A[i] = Integer.parseInt(st.nextToken());
            B.add(Integer.parseInt(st2.nextToken()));
        }
        Collections.sort(B);
        for (int i = 0; i < N; i++) {
            int a = A[i];
            int result = binarySearch(B, a);

            if (result == -1) {
                System.out.println(-1);
                return;
            }

            sb.append(B.get(result)).append(" ");
            B.remove(result);
        }
        System.out.println(sb.toString().trim());
    }

    private static int binarySearch(ArrayList<Integer> B, int a) {
        int left = 0;
        int right = B.size() - 1;
        int result = -1;

        while (left <= right) {
            int mid = (left + right) / 2;

            if (B.get(mid) >= a) {
                result = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return result;
    }
}

3. 해설

• 출력 할 때 A의 순서를 지켜야 하기 때문에 A 배열은 건들지 않고
  B만 정렬해서 이진 검색을 이용해서 최대한 빠르게 최소의 B값을 추출, 출력

 

• 문제점 : 정렬, 이진 검색 자체가 시간을 소요 시킨다
  어차피 조건을 만족하는 최소값이 필요한 거면 A와 B를 다 정렬해서 둘의 최소값끼리 비교하면된다
  하지만 그러면 출력할때 A의 순서가 꼬이기 때문에 이를 해결해야함
  → 최초 A의 인덱스를 기억하는 방식을 사용하자

4. 개선된 풀이

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

public class Main {

    private static class Node implements Comparable<Node> {
        int num;
        int idx;

        Node(int num, int idx) {
            this.num = num;
            this.idx = idx;
        }

        @Override
        public int compareTo(Node o) {
            return num - o.num;
        }
    }

    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringTokenizer st2 = new StringTokenizer(br.readLine());
        PriorityQueue<Node> A = new PriorityQueue<Node>();
        PriorityQueue<Integer> B = new PriorityQueue<Integer>();
        int[] result = new int[N];
        for (int i = 0; i < N; i++) {
            A.offer(new Node(Integer.parseInt(st.nextToken()), i));
            B.offer(Integer.parseInt(st2.nextToken()));
        }
        while (!A.isEmpty()) {
            Node a = A.poll();
            int b = B.poll();
            if (b >= a.num) {
                result[a.idx] = b;
            } else {
                System.out.println(-1);
                return;
            }
        }
        for (int i = 0; i < N; i++) {
            sb.append(result[i]).append(" ");
        }
        System.out.println(sb.toString().trim());
    }

}

• 우선순위 큐를 이용해서 항상 A와 B의 최소값 끼리 비교한다.
• 이때 a 보다 b가 크다면 해당 a의 index값에 b 값을 기록해두고
• 만약 a가 b보다 크다면 전체결과는 -1이 될 수 밖에 없다
  → 왜? a는 현재 A가 가진 최소값이고 현재 b로 만족시킬 수 있는 A의 값은 더이상 존재하지 않기때문에 결국 최종 결과도 -1이 될 수 밖에 없다

 

• 속도 개선 비교

	메모리	시간
기존 코드	72992 KB	2392 ms
개선된 코드	71120 KB	704 ms