[11650] 좌표 정렬하기

Arrays.sort는 최악의 경우, 시간 복잡도가 O(n^2)이라 사용하지 않았는데, 다른 사람들의 풀이를 보니, 이 문제에서는 사용해도 됐던 것 같다.

(Collections.sort는 Timsort를 사용하여 최악의 경우에도 O(n logn)을 보장한다. insert sort와 merge sort를 섞어쓴다고 한다.)

 

+

(Arrays.sort는 형에 따라 쓰는 알고리즘이 달라서 시간복잡도가 다르다고 한다.

int형으로 쓴다면, 자바는 Quicksort를 사용해서 최악의 경우 O(n^2)을 가지고,

Integer형으로 쓴다면, Mergesort로 O(n logn)을 가진다고 한다.

그렇다면 이 문제에서도 Integer로 쓴다면 걱정없이 Arrays.sort를 쓸 수 있을듯 하다.)

 

간단한 문제였음에도, 풀이 방법을 HashMap을 써가며 이렇게까지 풀었어야했나 싶은 생각이 들어서 많이 아쉽긴하다.

import java.io.BufferedWriter;
import java.io.IOException;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.Scanner;

public class Main {
	static int n,m;
	static int[] arr;
	static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	public static void main(String[] args) throws IOException {
		Scanner sc = new Scanner(System.in);
		
        // x값을 key로, y값은 x가 중복일 경우를 위해, ArrayList로 value
		HashMap <Integer, ArrayList<Integer>> map = new HashMap<Integer, ArrayList<Integer>>();
		int n = sc.nextInt();
		
		for(int i=0; i<n; i++) {
			int x = sc.nextInt();
			int y = sc.nextInt();
			ArrayList<Integer> list = new ArrayList<Integer>();
            // 같은 x값을 가진 좌표가 들어올 경우
			if(map.containsKey(x)) {
				list = map.get(x);
				list.add(y);
                // 정렬하기(정렬된 출력을 위해)
				Collections.sort(list);
			}else {
				list.add(y);
			}
            // x라는 키값에 list라는 value 넣어주기
			map.put(x, list);
		}
		
        // 좌표의 범위가 -100,000 ~ 100,000 이므로
		for(int i=-100000; i<=100000; i++) {
        	// 키값으로 i가 존재하는가?(= x가 i인 좌표가 입력되었는가?)  
			if(map.containsKey(i)) {
				for(int j=0; j<map.get(i).size(); j++) {
					bw.write( i + " " + map.get(i).get(j) + "\n");
				}
			}
		}
		
		bw.flush();
	}
}