ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • [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
Designed by Tistory.