정렬

정렬은 O(NlgN)이 걸리는 정렬을 사용해야 한다.
정렬을 직접 구현하는 것 보다는 언어에 구현되어 있는 것을 사용하는 것이 좋다.

C++은 algorithm 헤더 파일에 있는 std::sort를 사용한다.

int a[100];
sort(a, a+100);
vector<int> v;
sort(v.begin(), v.end());

• Java는 Arrays.sort나 Collections.sort를 사용한다.
• Arrays.sort(a): a를 오름차순으로 정렬한다.
• Arrays.sort(a, from, to): a의 [from,to)를 오름차순으로 정렬한다.
• Collections.sort(v): v를 오름차순으로 정렬한다.

int[] a = new int[n];
Arrays.sort(a);
ArrayList<Integer> v = new ArrayList<>();
Collections.sort(v);

• Python 리스트의 sort() 메소드를 사용한다.
•l.sort():l을 오름차순으로 정렬한다.

l.sort()
a.sort(reverse=True)

문제

11650 좌표 정렬하기

솔까말 그냥 파이썬이 강력하다.

import sys
sys.stdin = open("input.txt","r")
input=sys.stdin.readline

t = int(input())
p=[]

for _ in range(t):
    [a,b] = map(int,input().split())
    p.append([a,b])

p.sort()

for i in range(t):
    print(p[i][0], p[i][1])

11651 좌표 정렬하기 2

https://dailyheumsi.tistory.com/67
이번에는 lambda 함수를 사용하는 방법이다. 비교할 대상이 복수개인 경우 lambda 식을 사용해서 문제를 풀어내면 된다.

import sys
sys.stdin = open("input.txt","r")
input=sys.stdin.readline

t = int(input())
p=[]

for _ in range(t):
    [a,b] = map(int,input().split())
    p.append([a,b])

ans=sorted(p,key=lambda x:(x[1],x[0]))

for i in range(len(ans)):
    print(ans[i][0],ans[i][1])

Stable Sorting