글 읽기 - 파이썬 100% 틀렸습니다.

kdl5001 3년 전 0

파이썬에서 일부러 퀵소트를 구현해서 해보았습니다.

왠만한 질문글에서의 반례는 다 정확한 정답을 뱉는데 제출하면 100%에서 틀렸다고 나오네요.

지금 이틀째 끙끙 앓고 있습니다..

from sys import stdin
def setPivot(start, mid, end, index) :
    if arr[mid][index] < arr[start][index] :
        swap(mid, start)
    if arr[mid][index] > arr[end][index] :
        swap(mid, end)
    if arr[mid][index] < arr[start][index] :
        swap(mid, start)


def swap(a, b) :
    temp1 = arr[b][0]
    temp2 = arr[b][1]

    arr[b][0] = arr[a][0]
    arr[b][1] = arr[a][1]

    arr[a][0] = temp1
    arr[a][1] = temp2

def quickSort(start, end, index) :
    mid = ((end - start) // 2) + start

    setPivot(start, mid, end, index)

    if end - start < 3 :
        return

    swap(mid, end - 1)
    pivot = end - 1
    i = start + 1
    j = end - 1

    while i < j :
        while i < end and arr[i][index] <= arr[pivot][index] :
            i += 1

        while j > start and arr[j][index] >= arr[pivot][index] :
            j -= 1

        if i < j :
            swap(i, j)

    if i > pivot and j < pivot :
        quickSort(start, i - 1, index)
        return

    swap(i, pivot)
    quickSort(start, i - 1, index)
    quickSort(i + 1, end, index)


cnt = int(stdin.readline())
arr = [list(map(int, stdin.readline().split())) for _ in range(cnt)]
endTime = 0
meeting = 0

for index in range(0, 2) :
    quickSort(0, cnt-1, index)

for i in range(0, cnt) :
    if arr[i][0] >= endTime :
        meeting += 1
        endTime = arr[i][1]

print(meeting)

ghghgh777 3년 전 1

0 1

1 2

2 2

2 3

3 3

에서 4가 나오네요.

kdl5001 3년 전 0

감사합니다 ㅠㅠ 열심히 해볼게요

kdl5001 3년 전 0

퀵소트를 하기전에 피봇을 맨 오른쪽 한칸 전으로 이동시키는 작업이 있었는데, 더이상 바꿀게 없을때 빠지는 조건문에서 원래대로 되돌리는

작업을 수행했더니 정상적으로 나올 수 있었습니다. 몇일간의 싸움을 해결해주셔서 너무 감사합니다. ㅠㅠㅠ

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

문제

문제

출처

ICPC

파이썬 100% 틀렸습니다.

kdl5001 3년 전 0

ghghgh777 3년 전 1

kdl5001 3년 전 0

kdl5001 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말