달리기 경주 (출처 : 프로그래머스)
🧚
이번에는 문제의 길이는 짧은데 시간초과로 애를 먹었던 문제이다.
초기에 내가 하였던 접근은 다음과 같다.
callings, 즉 순서를 바꿔야 하는 상황일 때마다 players를 다시 탐색해서 같은 name이 나온다면 해당 기준으로 앞뒤를 바꿔주는 로직이었다.
처음에 문제를 봤을 때에는 왜이렇게 쉽지? 생각했는데
오산이었다.
제한 사항에서 players의 길이가 과도하게 길며 collings의 길이는 더 긴 것을 유의했었어야 했다.
어쩌면 이 점에서 힌트를 얻었을 수도 있다.
다시 돌아와보자면 결론적으로는 기존 나의 로직이라면 최악의 경우에는 50000 * 1000000 시간 복잡도가 날 수도 있다는 말이다.
때문에 이중반복문을 피하도록 최대한 짜야 했다.
코드 길이로 보면 굉장히 짧은데 중간중간에 집중력이 끊겼던 것 같다.
포인트는 간단했다.
딕셔너리를 이용해 player 당 위치를 value를 기억한다.
그 후 value를 이용해 players 배열에 접근해 직접 위치를 바꾼다.
그 후 딕셔너리의 value 값 또한 바꾼 위치를 적용해준다.
📌
def solution(players, callings):
answer = []
dic = {}
i = 0
for player in players:
dic[player] = i
i += 1
for calling in callings:
pt = dic[calling]
fw = pt - 1
players[pt] = players[fw]
players[fw] = calling
dic[calling] -= 1
dic[players[pt]] += 1
answer = players
return answer