[파이썬/Python] 백준 11651번 좌표 정렬하기 2

[파이썬/Python] 백준 11651번 좌표 정렬하기 2

11651번: 좌표 정렬하기 2

---

문제

2차원 평면 위의 점 N개가 주어진다. 좌표를 y좌표가 증가하는 순으로, y좌표가 같으면 x좌표가 증가하는 순서로 정렬한 다음 출력하는 프로그램을 작성하시오.

입력

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

출력

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

예제 입력

5
0 4
1 2
1 -1
2 2
3 3

예제 출력

1 -1
1 2
2 2
3 3
0 4

풀이 1

sort key 로 x, y 둘 다 고려할 경우

import sys
lst = sys.stdin.readlines()[1:]  # 입력 받은 점들의 리스트

# y좌표를 기준으로 오름차순 정렬, y좌표가 같으면 x좌표를 기준으로 오름차순 정렬
lst.sort(key=lambda x: (int(x.split()[1]), int(x.split()[0])))  

print("".join(lst))  # 정렬된 결과 출력

입력 받은 점들의 개수를 N이라고 할 때, 리스트에 입력을 저장하는 부분은 O(N) 시간이 소요된다.
lst.sort() 함수는 파이썬의 Timsort 알고리즘을 사용하며, 최악의 경우 O(NlogN)의 시간 복잡도를 가진다.
결과 출력은 O(N) 시간이 소요된다.
따라서, 전체적인 시간 복잡도는 O(NlogN)이다.

풀이 2

x 값을 나눠 y에 더해 sort key 를 하나로 통합

import sys

def cond(dot):
    x, y = dot.split()  # 입력 점의 x, y 좌표 추출
    return int(y) + int(x)/1000000  # y 좌표에 x 좌표의 소수 부분을 더한 값으로 정렬 기준 설정

dots = sorted(sys.stdin.readlines()[1:], key=lambda x: cond(x))  # 입력 받은 점들을 정렬 기준에 따라 정렬
print(''.join(dots))  # 정렬된 결과 출력

cond 함수에서는 y 좌표에 x 좌표의 소수 부분을 더한 값을 반환한다.
x 좌표의 소수 부분은 최댓값이 0.999999이고, 이를 더할 때 y 좌표의 값과 겹치지 않기 위해 적절한 범위로 조정해주어야 한다.
따라서, x 좌표를 1,000,000으로 나누어 소수 부분을 표현하여 y 좌표와 겹치지 않도록 조정한 것이다.

 

주어진 범위가 -100,000부터 100,000까지인데, 범위에 따라서 200,000 으로 나눠도 가능한가?
네, 주어진 범위가 -100,000부터 100,000까지이므로 x 좌표의 소수 부분은 최대 0.999999이다. 따라서 20만으로 나누어도 충분히 정밀한 값을 얻을 수 있다. 1,000,000으로 나누는 대신 20만으로 나눌 경우의 성능 차이는 거의 없을 것으로 예상된다.

1,000,000 으로 나눴을 때와 200,000 으로 나눴을 때

실제로 백만으로 나누는 대신 20만으로 나누는 것이 성능에 미치는 영향은 매우 작을 것이다. 두 경우 모두 소수점 아래 여섯 자리까지의 정밀도를 가지므로 결과적으로 동일한 정렬이 이루어진다.

 

그렇다면 100,000 으로도 나누어 떨어질텐데 가능할까?
y=3, x=-1의 cond 값은 3 + (-0.00001) = 2.99999가 되고,
y=2, x=99999의 cond 값은 2 + (99999/100000) = 2.99999가 된다.
따라서, 10만으로 나누어도 위 두 점이 동일한 값을 가지게 되므로, 동일한 값이 있는 경우 충돌이 발생한다. 즉, 정확한 정렬 결과를 얻기 위해서는 더 높은 정밀도가 필요하다. 

 

시간 복잡도가 같음에도 성능 차이가 발생 이유는?

1번 코드

2번 코드

두 코드는 모두 O(NlogN)의 시간 복잡도를 가지며, 입력 점들을 정렬하는데 소요되는 시간은 동일하다.
성능 차이가 발생하는 이유는 정렬 기준에 차이가 있기 때문이다. 첫 번째 코드는 lst.sort()를 사용하여 y좌표를 기준으로 오름차순 정렬하고, y좌표가 같은 경우 x좌표를 기준으로 오름차순 정렬한다.
두 번째 코드에서는 sorted() 함수를 사용하여 입력 받은 점들을 정렬하는데, key 함수로 cond(x)를 사용한다. cond() 함수는 y 좌표에 x 좌표의 소수 부분을 더한 값을 반환하는데, 이를 정렬 기준으로 사용한다.
따라서, 두 코드는 서로 다른 정렬 기준을 사용하고 있으며, 정렬 기준에 따라 결과가 달라질 수 있다. 성능 차이는 정렬 기준에 의해 발생하는 차이로 인해 나타날 수 있다. 실제로 입력 점들의 분포와 정렬 기준에 따라 어떤 코드가 더 효율적인지는 경우에 따라 다를 수 있다.

sort key lamda 에서 정렬 우선순위가 여러개여도 시간복잡도에는 차이가 없는가?
정렬 기준이 여러 개일 때에도 시간 복잡도에는 차이가 없다. 정렬 알고리즘의 시간 복잡도는 주로 입력 크기에 따라 결정되는데, 정렬 기준의 개수에는 영향을 미치지 않는다. 정렬 알고리즘은 기본적으로 비교 연산을 사용하여 요소들을 비교하고 정렬하는데, 정렬 기준의 개수에 상관없이 비교 연산의 수는 동일하다.
따라서, 정렬 기준이 여러 개일 때에도 시간 복잡도는 정렬 알고리즘에 의해 결정되며, 기본적으로 O(NlogN)이다. 정렬 기준의 개수가 늘어난다고 해도, 정렬 알고리즘의 복잡도에는 영향을 미치지 않는다.

 

참고자료

로그인

Using a lambda as key within builtin string sort(), hard to identify Big-O

파이썬 정렬, 다중 조건으로 한 번에 하기.