글 읽기 - 11870 파이썬 부디 시간초과 해결 도움 부탁드려요 ㅠㅠ

wjddn3711 2년 전 0

계속 시간초과 뜨다가 여기서 더이상 줄일수가 있을까 싶을 정도로 막막하네요...

sort()를 그냥 사용하지 않고 다른 정렬 방법을 사용해야할까요?

import sys
n = int(sys.stdin.readline())
ar = list(map(int,sys.stdin.readline().split()))
dicAr = sorted({key:0 for key in ar}) # ar에 담긴 값들을 하나씩 담아주고 정렬한다
for i in range(n):
    if i==n-1:
        print(dicAr.index(ar[i]))
    else:
        print(dicAr.index(ar[i]),end=' ')

djm03178 2년 전 1

정렬은 전혀 문제되지 않습니다. 느린 부분은 index입니다. list.index는 리스트의 처음부터 하나씩 차례대로 보면서 해당 원소를 찾기 때문에 리스트의 길이에 비례하는 시간이 걸립니다. 이를 모든 원소에 대해 수행하고 있으니 총 시간 복잡도는 O(N^2)이 됩니다.

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

문제

문제

출처

ICPC

11870 파이썬 부디 시간초과 해결 도움 부탁드려요 ㅠㅠ

wjddn3711 2년 전 0

djm03178 2년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말