글 읽기 - 파이썬 시간초과

wodus0129 3년 전 0

다음과 같이 작성했더니 시간초과가 발생합니다....

무엇이 문제인가요?

n = int(input())

list_x, list_y, temp_x, temp_y = [], [], 0, 0

for i in range(0, n, 1):
    x, y = map(int, input().split())
    list_x.append(x)
    list_y.append(y)

for i in range(0, n - 1, 1):
    for j in range(i + 1, n, 1):
        if list_x[i] >= list_x[j]:
            if list_x[i] > list_x[j]:
                temp_x = list_x[i]  # x좌표의 오름차순 정렬 시작
                list_x[i] = list_x[j]
                list_x[j] = temp_x  # x좌표의 오름차순 정렬 완료
                temp_y = list_y[i]  # y좌표의 오름차순 정렬 시작
                list_y[i] = list_y[j]
                list_y[j] = temp_y  # y좌표의 오름차순 정렬 완료
            elif list_x[i] == list_x[j]:
                if list_y[i] > list_y[j]:
                    temp_y = list_y[i]
                    list_y[i] = list_y[j]
                    list_y[j] = temp_y
for i in range(0, n, 1):
    print(list_x[i], list_y[i])

ikeelee7742 3년 전 0

N이 최대 10만이라 O(N^2) 풀이보단 O(NlogN) 풀이로 풀어야 합니다

wodus0129 3년 전 0

O(NlogN) 이라뇨?

ikeelee7742 3년 전 2

버블정렬이나 삽입, 선택정렬처럼 반복문을 두번 사용하는 풀이는 시간초과가 나고

퀵정렬이나 병합정렬같은 시간복잡도가 더 효율적으로 나오는 방법을 사용해야 합니다.

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

문제

문제

출처

ICPC

파이썬 시간초과

wodus0129 3년 전 0

ikeelee7742 3년 전 0

wodus0129 3년 전 0

ikeelee7742 3년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말