Python 시간 초과

1
2
3
4
5
def solution(players, callings):
    for x in callings:
        rank = players.index(x)
        players[rank], players[rank-1] = players[rank-1], players[rank]
    return players

• 

  2줄과 3줄이 독립적으로 callings 배열(크기:M)과 players 배열(크기:N)의 크기에 비례하기 때문에 시간복잡도는 둘의 곱인 O(MN)이 되어 이 방법으로 풀 수 없습니다. 일반적으로 O(n)에서 n의 값이 1억을 넘으면 통과가 어렵다고 보면 되는데, 문제 조건을 보면 백만*5만=5백억이라는 수가 나오죠. 이 문제는 양방향 인덱싱을 이용해야 하고, 그러기 위해선 딕셔너리 두 개 또는 딕셔너리 하나와 리스트 하나가 필요합니다.

  mgcpython―2023.04.12 05:02