-
[PS]좌표 정렬하기Problem Solving 2020. 12. 10. 22:57
단어 정렬하기와 비슷한 문제.
좌표가 입력되고 해당 좌표를 x좌표의 오름차순으로 정렬하고,
x좌표가 같은 경우 다음은 y좌표로 정렬하여 출력해야 하는 문제이다.
import math def mergesort(entries): if isinstance(entries,list) and len(entries) > 1 : pivot = math.floor(len(entries)/2)-1 first = mergesort(entries[:pivot+1]) second = mergesort(entries[pivot+1:]) return merge(first,second) else: return entries def merge(first,second): unit=[] if not isinstance(first,list): first = [first] if not isinstance(second,list): second = [second] first_p = second_p = 0 while first_p < len(first) and second_p < len(second): firstr = list(map(int,first[first_p])) secstr = list(map(int,second[second_p])) if firstr[0]<secstr[0]: unit.extend([first[first_p]]) first_p+=1 elif secstr[0]<firstr[0]: unit.extend([second[second_p]]) second_p+=1 else: if firstr[1]<=secstr[1]: unit.extend([first[first_p]]) first_p+=1 elif secstr[1]<firstr[1]: unit.extend([second[second_p]]) second_p+=1 if first_p >= len(first) and second_p < len(second): unit.extend(second[second_p:]) else: unit.extend(first[first_p:]) return unit num = int(input()) entries=[] for n in range(0,num): entries.extend([input().split()]) entries = mergesort(entries) for x in entries: for y in x: print(y,end=' ') print('')
정렬 알고리즘은 병합 정렬을 응용하였다.
단어 정렬과 로직이 비슷해서 조금만 바꿔서 하면 쉽게 풀릴 줄 알았으나,
어째 쉽지가 않았다.
위 알고리즘의 로직은 다음과 같다.
1.병합 정렬에 따라 각 리스트의 크기가 1이 될 때까지 계속해서 절반으로 쪼갠다.
2.리스트의 크기가 1이 되면, 첫번째를 first, 두 번째를 second로 해서 병합을 실행한다.
3.병합을 실행하는 과정에서, 한 덩어리에 여러 개의 좌표가 포함되어 있을 수 있으므로, 각각의 포인터를 둔다.
4.해당 포인터 인덱스의 좌표를 불러와 비교를 진행.
5.어느쪽이 더 작은가를 판단하여, 작은 쪽을 결과 리스트에 붙이고 작았던 리스트의 포인터를 1 증가 시킨다.
6.위 과정을 반복하여 어느 쪽 하나가 끝에 다다르면, 나머지 리스트의 남은 부분을 결과에 가져다 붙인다.
7.이런 식으로 끝까지 정렬을 진행하며 합병을 완료.
'Problem Solving' 카테고리의 다른 글
[PS] 수 찾기 (0) 2020.12.05 [PS]수 정렬하기 3 (0) 2020.12.03 [PS] 단어 정렬하기 (0) 2020.12.02 [PS] 백준 - 수 정렬하기 2 (0) 2020.11.19