글 읽기 - 버블정렬 질문이요ㅜㅠ

dlgpqls98 3년 전 0

시간초과 나왔는데 왜나온지 모르겠어요ㅜㅠ

O(n^2)이면 1초안에 못풀지 않나요??ㅜㅠ

n=int(input())
def bubble_sort(arr):
    for i in range(len(arr) - 1, 0, -1):
        swapped = False
        for j in range(i):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
        if not swapped:
            break
    return arr

print(bubble_sort(list(map(int,input().split()))))

skeep194 3년 전 0

이문제는 버블 정렬을 그대로 수행하면 시간 초과를 받습니다.

swap 횟수만 알 수 있는 더 빠른 방법이 있습니다.

herdson 3년 전 1

이 문제는 반전 인덱스라는 나름 잘 알려진 문제 부류입니다. 세그먼트 트리나 병합 정렬을 이용하여 풀 수 있습니다.

https://salepark.tistory.com/1...

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

문제

문제

출처

ICPC

버블정렬 질문이요ㅜㅠ

dlgpqls98 3년 전 0

skeep194 3년 전 0

herdson 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말