[백준] 11650번_좌표 정렬하기(Java)

문제 풀이

백준의 11650번 문제입니다. 문제 출처

(1) 문제 파악

x,y 좌표를 가진 점이 있을 때, 점을 정렬시키는 문제입니다.

(2) 문제 풀이 방법 생각하기

x좌표를 정렬하고, 같은 x좌표일 경우 y좌표를 정렬하면 되므로 x좌표를 key로 가지는 Map을 사용해 문제를 풀 수 있습니다.

Map<x좌표, y좌표 리스트>

(3) 시간 복잡도 확인

시간 제한은 1초 입니다. 즉, 대략 1억번 연산 안에 문제를 해결해야 합니다.

주요한 풀이인 정렬에서는 Collections.sort()를 사용할 예정이며, Collections.sort()의 시간 복잡도는 평균/최악 O(nlogn)입니다. x 좌표 정렬 후 y 좌표를 정렬하는 과정에서 두 번 sort 함수를 사용하게 되는데 N의 최대 값이 100,000이므로 가능합니다.

(4) 구현

입력의 크기가 작으므로 파도반 수열을 미리 계산해놓고 원하는 P(N)을 출력하는 방식으로 작성하였습니다.

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        Map<Integer, ArrayList<Integer>> map = new HashMap<>();

        StringTokenizer st;
        for(int i=0; i<N; i++) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            
            if(map.containsKey(x)) map.get(x).add(y);
            else {
                map.put(x, new ArrayList<>());
                map.get(x).add(y);
            }
        }

        List<Integer> x_list = new ArrayList<>(map.keySet());
        Collections.sort(x_list);

        for(int x: x_list) {
            List<Integer> y_list = map.get(x);
            Collections.sort(y_list);

            for(int y: y_list) {
                System.out.println(x + " " + y);
            }
        }
    }
}