[PS]좌표 정렬하기

단어 정렬하기와 비슷한 문제.

좌표가 입력되고 해당 좌표를 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.이런 식으로 끝까지 정렬을 진행하며 합병을 완료.