글 읽기 - 반례가 무엇인지 모르겠습니다...

cr2at2 4년 전 0

퀵정렬을 이용해

x좌표를 먼저 비교하고 같으면 y좌표도 비교하도록 퀵정렬을 구현했습니다.

질문에 있는 반례도 넣어봤으나 출력이 제대로 나오는거 같아서 도움을 청합니다.

import sys


n=int(sys.stdin.readline())
xy_list=[[int(i) for i in sys.stdin.readline().split()] for _ in range(n)]

#퀵정렬
def quicksort(start,end,li):
    if start>=end:
        return li
    pivot=start
    left=start+1
    right=end
    while left<=right:
        while li[left][0]<=li[pivot][0] and left<end:   #x좌표가 피봇보다 크다면
            if li[left][0]==li[pivot][0]:   #x가 같다면 y비교
                if li[left][1]<=li[pivot][1]:
                    left+=1
                else:
                    break
            else:
                left+=1
        while li[right][0]>=li[pivot][0] and right>pivot:
            if li[right][0]==li[pivot][0]:
                if li[right][1]>=li[pivot][1]:
                    right-=1
                else:
                    break
            else:
                right-=1
        if left<right:
            li[left],li[right]=li[right],li[left]
            left+=1
            right-=1
        else:
            li[pivot],li[right]=li[right],li[pivot]

    quicksort(start,right,li)
    quicksort(right+1,end,li)


quicksort(0,len(xy_list)-1,xy_list)
for i in range(len(xy_list)):
    print(xy_list[i][0],xy_list[i][1])

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

반례가 무엇인지 모르겠습니다...

cr2at2 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말