21.08.25 기록

백준 알고리즘 11650 풀이

🎆나의 오답(시간초과)

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

public class B11650 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        final int RANGE = 100_000;

        int N = Integer.parseInt(br.readLine());
        int[] countingX = new int[2*RANGE + 1];
        int[] y = new int[2*RANGE + 1];

        for(int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            int n = Integer.parseInt(st.nextToken()) + RANGE;
            int m = Integer.parseInt(st.nextToken()) + RANGE;
            countingX[n]++;
            y[m] = n;
        }

        StringBuilder sb = new StringBuilder();
        boolean[] check = new boolean[2*RANGE + 1];
        int cnt = 0;
        for(int i = 0; i < countingX.length; i++) {
            if(cnt == N) { break; }
            for(int j = 0; j < y.length; j++) {
                if(countingX[i] < 1) { break; }
                if(y[j] == i && !check[j]) {
                    cnt++;
                    sb.append(i-RANGE).append(" ").append(j-RANGE).append("\n");
                    check[j] = true;
                    countingX[i]--;
                }
            }
        }
        System.out.println(sb);
    }
}

🎆해설(메모리 50.5MB, 시간 784ms로 통과)

-Comparator 인터페이스를 람다 형태로 구현하여 Arrays.sort() 기능을 확장한 풀이다.

• Comparable vs Comparator
• Comparable은 ‘자기 자신과 매개변수 객체를 비교’ 하고, Comparator는 ‘두 매개변수 객체를 비교’ 한다.
  
• 두 인터페이스의 메소드를 재정의 후, + 또는 -를 사용하여 값을 반환할 때 Overflow 또는 Underflow가 발생할 여지가 반드시 확인해야할 필요가 있다.
  
• Comparator를 구현할 때 익명 객체를 사용하면 메소드를 사용하는 코드에 더 집중할 수 있다.
  
• 자바는 기본적으로 오름차순 정렬을 하며, 두 수를 비교할 때 결과가 음수면 원소의 위치를 교환하지 않고 양수일 경우 위치를 교환한다.
  

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

public class B11650 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        StringTokenizer st;
        int[][] numbers = new int[N][2];
        for(int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            numbers[i][0] =  Integer.parseInt(st.nextToken());
            numbers[i][1] =  Integer.parseInt(st.nextToken());
        }

        //sort(T[] a, Comparator<? super T> c) Comparator는 compare()를 구현해야한다.
        Arrays.sort(numbers, (e1, e2) -> {

            //return 값이 음수이면 요소의 위치를 바꾼다.
            if(e1[0] == e2[0]) { return e1[1] - e2[1]; }
            else { return e1[0] - e2[0]; }
        });

        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < N; i++) {
            sb.append(numbers[i][0]).append(" ").append(numbers[i][1]).append("\n");
        }
        System.out.println(sb);
    }
}