백준 11650번: 좌표 정렬하기

2차원 평면의 x, y의 좌표가 N개 주어진다.

받은 N개의 좌표를 x를 기준으로 그리고 x가 같다면 y를 기준으로 정렬하여 출력하는 문제이다.

 

x와 y를 이차원배열로 받아서 정렬한다고 했을 때, x, y 두 값이 따로따로 움직이면 의미가 없다고 생각해서

클래스를 만들어서 x, y값을 저장했다.

그 뒤로 x의 값만을 따로 저장하는 배열을 하나 만들고, 그 배열을 정렬해주었다.

정렬한 x를 기준으로 클래스 배열에서 작은 x를 뽑아내고 그 중에 x가 같다면 y를 기준으로 정렬하게 하였다.

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

public class Main {
   public static void main(String[] args) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
      int N = Integer.parseInt(br.readLine());
      XY[] xy = new XY[N];
      int[] Xs = new int[N];
      for (int i = 0; i < N; i++) {
          StringTokenizer st = new StringTokenizer(br.readLine());
          xy[i] = new XY(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
          Xs[i] = xy[i].x;
      }
      br.close();
      
      XY[] sort = new XY[N];
      Arrays.sort(Xs);
      int index = 0;
      for (int i = 0; i < N; i++) {
          index++;  //중복되는 x의 개수수
          if (i != N - 1 && Xs[i] == Xs[i + 1]) continue; //중복되는 x는 한번만
          
          int yIdx = 0;
          int[] temp = new int[index];
          for (int j = 0; j < N; j++) {
              if( Xs[i] == xy[j].x ) {
                  temp[yIdx++] = xy[j].y;
              }
          }
          
          Arrays.sort(temp);
          for (int j = 0; j < yIdx; j++) {
              bw.write(Xs[i] + " " + temp[j] + "\n");
          }
          index = 0;
      }
      
      bw.flush();
      bw.close();
   }
}

class XY {
    int x;
    int y;
    XY(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

위는 그렇게 만들어본 코드인데 시간 초과가 붙었다.

그래서 정렬하는 알고리즘이 시간 복잡도를 올리는 것 같아서 정렬을 하여 작은 x를 찾아내는 것이 아니라

가장 작은 x를 찾고, 그 x와 연결된 y를 찾고 찾은 수를 문제의 입력 조건보다 크게 하여 걸러내는 방식으로

새로운 코드를 만들었다. 

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

public class Main {
   public static void main(String[] args) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
      int N = Integer.parseInt(br.readLine());
      XY[] xy = new XY[N];
      for (int i = 0; i < N; i++) {
          StringTokenizer st = new StringTokenizer(br.readLine());
          xy[i] = new XY(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
      }
      br.close();
      
      for (int i = 0; i < N; i++) {
        int smX = 100001; 
        for (int j = 0; j < N; j++) {
            if (smX > xy[j].x) smX = xy[j].x;
        }
        int smY = 100001;
        int index = 0;
        for (int j = 0; j < N; j++) {
            if (smX != xy[j].x) continue;
            else if (smY > xy[j].y) {
                smY = xy[j].y;
                index = j;
            }
        }
        bw.write(smX + " " + smY + "\n");
        xy[index].x = 100002;
        xy[index].y = 100002;
      }
      
      bw.flush();
      bw.close();
   }
}

class XY {
    int x;
    int y;
    XY(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

하지만 이 코드 역시 시간 초과가 되었고, 결국 검색을 하여 새로운 방법을 찾아냈다.

 

Arrays.sort()는 Comparator 인터페이스를 오버라이딩하는 것으로 정렬 기준을 바꿔줄 수 있는데

이를 통해 2차원 배열에서도, 그리고 해당 문제에서 요구하는 형식으로도 정렬할 수 있게 된다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
import java.util.Arrays;
import java.util.Comparator;


public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int n = Integer.parseInt(br.readLine());
		int[][] arr = new int[n][2];
		for (int i = 0; i < n; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			arr[i][0] = Integer.parseInt(st.nextToken());
			arr[i][1] = Integer.parseInt(st.nextToken());
		}
		br.close();

		Arrays.sort(arr, (e1, e2) -> {
			if (e1[0] == e2[0]) return e1[1] - e2[1];
			else return e1[0] - e2[0];
		});
		
		for (int i = 0; i < n; i++) {
			bw.write(arr[i][0] + " " + arr[i][1] + "\n");
		}
        bw.flush();
        bw.close();
	}
}

해당 코드는 검색해서 나온 내용을 바탕으로 어떻게 따라해서 만들어낸 코드이다.

다행이 문제는 풀 수 있었으나, 해당 용법을 아직 완전히 이해하지는 못하여서 더 공부해봐야겠다.