프로그래머스 | 달리기 경주 (python)

 

다들 그랬던 것 같은데,

첫번째 풀이는 일단 players배열을 중심으로 callings배열의 요소를 한개씩 비교해가면서 자리를 바꿔주는 코드를 작성하였다. 

결론은 시간초과.

왜인지 문제를 다시 봐보면

callings의 최대 길이 = 1,000,000

players의 최대 길이 = 50,000

이므로 O(1)로 로직을 짜야 시간초과를 피할 수 있다.

시간초과를 피하기 위해서 딕셔너리를 사용하여 코드를 다시 작성했다.

 

>> 최종 코드 <<

def solution(players, callings):
    rankDict = {}
    playersDict = {}

    for idx, player in enumerate(players):
        rankDict[idx] = player
        playersDict[player] = idx        
    for j in callings:
        frontPlayerIdx = playersDict[j]-1
        playerIdx = playersDict[j]
        secondPlayer = rankDict[frontPlayerIdx]
        
        rankDict[playerIdx] , rankDict[frontPlayerIdx] = rankDict[frontPlayerIdx] , rankDict[playerIdx] 
        playersDict[j] , playersDict[secondPlayer] = playersDict[secondPlayer] ,playersDict[j]
        
    players = sorted(playersDict, key=playersDict.get)    

    return players

 

enumerate()를 사용해서 플레이어와 그 인덱스를 짝지어서 딕셔너리에 넣어줬다.

찾아가기 쉽게끔 키와 밸류를 바꾼 딕셔너리를 하나 더 생성하고

callings 배열의 요소 순서대로 딕셔너리를 통해 접근해서 플레이어의 순서와 인덱스를 바꿔줬다.

마지막으론 playersDict를 정렬해서 출력한다.