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

아래 프로그래머스 로고를 클릭하면 해당 문제로 이동합니다 😀

풀이과정

---

간단하게 생각하면, 이름이 불린 선수랑 그 앞에 있는 선수의 자리를 바꿔주면 된다.

def solution(players, callings):
    answer = []

    for call in callings:
        idx = players.index(call)
        players[idx-1], players[idx] = players[idx], players[idx-1]

    return players

근데 이렇게 간단한 문제일리가 없지. 시간초과님이 저를 반기시네요 ㅎㅎ;

어떻게 할 수 있을까 하다가 선수이름마다 등수를 그냥 같이 딕셔너리로 기록하면 어떨까 했다.
딕셔너리 자료형은 key값은 고유하고 value가 각자 달려있으니까 이 value를 변경해주면 되지않을까 라고 생각했다.

ranks라는 딕셔너리를 하나 만들자.
key: value쌍에서 key는 players에 있는 선수들의 이름, value는 players에 선수들이 있던 인덱스가 된다.

>>> ranks
{'mumu': 0, 'soe': 1, 'poe': 2, 'kai': 3, 'mine': 4}

그리고 이제 이름이 불린 선수들의 순위를 바꿔주자.
바뀐 선수의 순위를 idx에 저장해두고, 순위를 -1 해줬다.
그리고 rank(player[idx-1])에 있던 선수의 순위를 +1 해준다.

마지막으로 원래 코드처럼 스왑을 해주면 된다.

📢 참고 : index의 시간 복잡도가 O($n$)인데, 이걸 callings를 도는 for문에서 체크하면 시간복잡도가 O($n^2$)가 되어 시간초과가 발생한다.

코드

---

def solution(players, callings):
    answer = []
    ranks = {name: rank for rank, name in enumerate(players)}
    for call in callings:
        idx = ranks[call]

        ranks[call] -= 1
        ranks[players[idx-1]] += 1

        players[idx-1], players[idx] = players[idx], players[idx-1]

    return players

결과

---