[Python]정렬 백준 11650

   문제

   https://www.acmicpc.net/problem/11650

좌표를 정렬하는 문제이다.

x값을 기준으로 정렬하다가 같은값이나오면 y값으로 정렬하면 될거같다.

2차원원배열을 이용해 담았고 여러가지 알고리즘을 통해 정렬을 구현해봤다.

선택정렬을 통해 구현한 결과 시간초과가 떴다.

11650선택정렬.py

조금 더빠른 퀵정렬을 통해 구현해봤다.

11650퀵정렬.py

이번엔 잘 정렬되는거 같은데 틀렸다고 나온다.

문제가 무엇인지 파악할수가없다. 질문을 올려놓긴 했지만 언제 답을 줄지 앐 수없어서 

힙소트로 제출했다.

혹시 반례나 코드에 문제점이 무엇인지 안다면 댓글로 알려주시면 감사하겠습니다.

아래는 힙소트로 구현한 코드이다

import sys
 
n=int(sys.stdin.readline())
xy_list=[[int(i) for i in sys.stdin.readline().split()] for _ in range(n)]
#힙정렬
#힙만들기
def heap(li):#힙구조 만들기
    for i in range(len(li)):
        c=i
        while c>0:
            root=(c-1)//2
            if li[c][0]>li[root][0]:
                li[c],li[root]=li[root],li[c]
            elif li[c][0]==li[root][0]:
                if li[c][1]>li[root][1]:
                    li[c], li[root] = li[root], li[c]
            c=root
 
 
 
def heapsort(li):
    heap(li)#최대힙 구조로 만들어줌
    for i in range(len(li)-1,0,-1):
        li[0],li[i]=li[i],li[0]
 
 
        root=0
        c=0
        while(c<i):
            c=2*root+1
            if c<i-1 and li[c][0]<li[c+1][0]:#범위를 벗어나지 않는선에서 두자식중 큰놈 고르기기
               c+=1
            elif c<i-1 and li[c][0]==li[c+1][0]:
                if li[c][1]<li[c+1][1]:
                    c+=1
 
            if c<i and li[root][0]<li[c][0]:
                li[root],li[c]=li[c],li[root]
            elif c<i and li[root][0]==li[c][0]:
                if li[root][1]<li[c][1]:
                    li[root], li[c] = li[c], li[root]
            root=c
 
 
 
heapsort(xy_list)
for i in range(len(xy_list)):
    print(xy_list[i][0],xy_list[i][1])
 

이경우에는 성공했다.

병합정렬도 가능하겠지만 이건 나중에 시간나면 한번 해봐야겠다.