[백준 알고리즘] 11650 좌표 정렬하기 (21.05.09)

 

 

오늘은

 

바로바로

 

정렬 입니다요!!!!

 

 

 

---

 

 

그래서 오늘의 문제는

 

 

 

백준 11650번

 

 

 

입력

첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다.

 

 

출력

첫째 줄부터 N개의 줄에 점을 정렬한 결과를 출력한다.

 

 

문제 사이트 : www.acmicpc.net/problem/11650

11650번: 좌표 정렬하기

 

 

 

---

여기서 핵심 포인트!!!

 

 

- x, y를 어떻게 묶을 것인가!!!

 

 

- 정렬할 때 어떻게 비교할 것인가!!!

 

---

 

 

 

 

직접 작성해본 소스코드 및 간단한 설명

 

 

• 첫 번째 코드 !!!!!!

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.Scanner;

class Point {
	int x;
	int y;

	Point(int x, int y) {
		this.x = x;
		this.y = y;
	}
	
	int getX() {
		return x;
	}
	
	int getY() {
		return y;
	}
}


public class Main {
	static ArrayList<Point> list;
	static int N ;
	
	static void swap(int first, int second) {
		Point tmpFirst = list.get(first);
		list.set(first, list.get(second));
		list.set(second, tmpFirst);
	}
	
	static void sorting() {
		for(int i = 0; i< N-1; i++) {
			int least = i;
			for(int j = i+1; j < N; j++) {
				if(list.get(j).getX() < list.get(least).getX()) {
					least = j;
				}
				else if (list.get(j).getX() == list.get(least).getX()) {
					if(list.get(j).getY() < list.get(least).getY()) {
						least = j;
					}
				}
			}
			swap(i, least);
		}
	}
	
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();

        list = new ArrayList<Point>();
        for(int i = 0; i< N; i++){
           int x = sc.nextInt();
           int y = sc.nextInt();
           list.add(new Point(x,y));
        }

        sorting();
        for(int i = 0; i< N; i++) {
        	System.out.println(list.get(i).getX()+ " " + list.get(i).getY());
        }
        
    }

}

 

어떻게 풀었는 지 말해보자면...

 

 

• Point 클래스 만들어서 x, y 저장하기

 

• 선택 정렬 하기

 

---

사실 위 문제는 2초 안에 풀어야하기 때문에

 

복잡도가 높은 선택정렬을 사용하면

 

틀린다!!!!!!

---

 

 

• list.set() 사용해서 SWAP 해주기!!!

 

 

 

 

 

그리하여 .....

 

 

 

•  두 번째 코드 !!!!!!!!!!!!!!!!!1

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.Scanner;

class Point {
	int x;
	int y;

	Point(int x, int y) {
		this.x = x;
		this.y = y;
	}
	
	int getX() {
		return x;
	}
	
	int getY() {
		return y;
	}
}


public class Main {
	static ArrayList<Point> list;
	static int N ;
	
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();

        list = new ArrayList<Point>();
        for(int i = 0; i< N; i++){
           int x = sc.nextInt();
           int y = sc.nextInt();
           list.add(new Point(x,y));
        }

        Collections.sort(list, new Comparator<Point>() {
            @Override
            public int compare(Point s1, Point s2) {
                if (s1.getX() == s2.getX()) {
                    return s1.getY() - s2.getY();
                } else{
                    return s1.getX() - s2.getX();
                }
            }
        });

        for(int i = 0; i< N; i++) {
        	System.out.println(list.get(i).getX()+ " " + list.get(i).getY());
        }
        
    }

}

 

바뀐 부분을 설명하자면 ...

 

 

 

기존에 java에서 제공하는 라이브러리를 이용했다는 것이 KEYPOINT 이다!!!!

 

 

 

• Collections.sort() 사용하기

 

• Comparator 사용해서 정렬 조건 적어주기!!!!!!!!!!!

 

 

 

 

 

 

---

 

 

백준 알고리즘

 

채점 결과!!!

 

 

 

다행히 맞았습니다!!

 

백준 알고리즘 11650번 채점 결과

 

 

 

 

 

 

 

 

---

스터디하면서 나온 더 좋은 방법들

• Vector 의 사용
• C++ 에서 sort() 함수 사용 시 compare 함수 사용
• 선택 정렬은 안 좋으니 퀵 정렬 사용하는 것 추천