섹션 6. Sorting and Searching(정렬, 이분검색과 결정알고리즘) 7. 좌표 정렬

문제

• N개의 평면상의 좌표(x, y)가 주어지면 모든 좌표를 오름차순으로 정렬하는 프로그램을 작성하세요.
• 정렬기준은 먼저 x값의 의해서 정렬하고, x값이 같을 경우 y값에 의해 정렬합니다.

입력

• 첫째 줄에 좌표의 개수인 N(3<=N<=100,000)이 주어집니다.
• 두 번째 줄부터 N개의 좌표가 x, y 순으로 주어집니다. x, y값은 양수만 입력됩니다.

출력

• N개의 좌표를 정렬하여 출력하세요.

입출력 예제

---

풀이방식

이번 문제는 Comparable 를(을) 사용하여 푸는 문제이다.

---

설계과정

1. 클래스를 선언하여 좌표 값을 입력받는다.

2. x 좌표가 다르면 x 좌표를, x 좌표가 같으면 y 좌표를 비교하여 정렬한다.

3. Point 객체에 저장된 정렬한 좌표들을 

---

풀이과정

1. 값들을 입력받는 코드를 작성한다.

• 이 때 결과를 출력할 arr 배열은 Pointe 객체를 생성해서 호출함으로써 compareTo()를 통해 정렬된 값을 출력한다.

2. 객체를 만들어서 x, y 좌표 값을 저장한다.

• Point : Comparable 인터페이스의 구현체이다.
• Comparable 인터페이스 : 객체를 정렬하는 데 사용되는 인터페이스로, compareTo() 메소드를 정의하고 있다. 기본적으로 오름차순으로 정렬한다.
• Comparator 인터페이스 : 내림차순이나 아니면 다른 기준으로 정렬하고 싶을 때 사용할 수 있다.

3. compareTo 메소드를 오버라이딩하여 문제에 맞게 재정의한다.

• CompareTo() : 해당 객체와 전달된 객체의 순서를 비교한다.

4. 두 좌표값이 동일하면 y 좌표값을 통해 정렬한다.

• this.x : 현재 좌표
• o.x : 파라미터로 넘어온 좌표
• 음수 또는 0이면 객체의 자리가 그대로 유지되며, 양수인 경우에는 두 객체의 자리가 바뀐다.

5. 두 x 좌표값이 다르면 x 좌표값을 통해 정렬한다.

 

6. Collections.sort() 를 사용해서 배열을 정렬한다.

• Collections.sort() : Comparable 인터페이스를 통해 Point 객체를 정렬한다.
• 이 때 정렬의 기준은 내가 작성한 compareTo() 이다.

---

해당 글은 인프런 > 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비(김태원)강의를 참고하여 작성하였습니다.