[프로그래머스] 달리기 경주

https://school.programmers.co.kr/learn/courses/30/lessons/178871

 

프로그래머스

SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프

programmers.co.kr

오랜만에 프로그래머스 풀이를 진행하였다..

풀이

이문제는 단순하게 덤볐다가 시간초과가 나는 문제이다..

Python 내장 함수 index는 시간 복잡도가 O(N)이기 때문에 조심해서 사용해다 한다는 점을 다시한번 생각하게 되는 문제이다.

처음에 시간 초과가 난 코드는 단순하게 index의 위치를 탐색해 SWAP 하는 코드를 짰지만 68점 밖에 얻을 수 없었다.

조금더 시간을 효율적으로 사용하기 위해서, dictionary를 통해 구현을 진행하였다.

기존과 동일하게 swap을 진행해서, O(N + M)의 시간을 사용할 수 있다.

코드

'''
# 68.8 / 100.0
# players.index(i)가 O(N)이므로 시간초과 발생
 
def solution(players, callings):
    answer = []
    for i in callings :
        rank = players.index(i)
        user = players[rank]
        temp = players[rank - 1]
        players[rank - 1] = user
        players[rank] = temp
 
    return players
'''
def solution(players, callings):
    answer = {}
    for index, value in enumerate(players) :
        answer[value] = index
    for i in callings :
        index = answer[i]
        previous = index - 1
        previous_user = players[previous]
 
        players[previous], players[index] = players[index], players[previous]
 
        answer[i] = previous
        answer[previous_user] = index
 
    return players
 
print(solution(["mumu", "soe", "poe", "kai", "mine"],["kai", "kai", "mine", "mine"])) #["mumu", "kai", "mine", "soe", "poe"]
# kai -> mumu soe kai poe mine
# kai -> mumu kai soe poe mine
# mine -> mumu kai soe mine poe 
# mine -> mumu kai mine soe poe

1천등 안에 드는것이 목표이다..