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

문제 요약

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

 

경주에서 현재 등수 순서대로 선수들의 이름이 담긴 players 배열과 추월한 선수의 이름이 순서대로 담긴 callings 배열이 주어진다.

추월했을 때 앞에 있는 선수와 순서가 바뀌게 된다.

경주가 끝났을 때 선수들의 순서를 배열에 담아 반환하는 문제.

 

접근

배열을 사용할지 딕셔너리를 사용할지 고민하다가 딕셔너리를 사용하면 value값으로 key값을 찾아야될거라고 생각해서 코드가 복잡해질 것 같아 배열을 사용했다.

 

배열에서 추월한 선수와 추월 당한 선수의 위치를 swap시켜 결과값을 반환했다.

이렇게 풀었더니 시간초과가 났다.

players 배열의 최대 길이가 50,000이어서 그런 것 같다. 

 

최종 풀이에서는 딕셔너리를 2개 사용해서 풀었다.

seq 딕셔너리에는 이름:순서, name 딕셔너리에는 순서:이름을 저장해주었다.

 

추월이 발생할 때마다 seq와 name 딕셔너리의 value값을 변경해주었고,

마지막으로 name 딕셔너리값을 result 배열에 넣어 반환해주었다.

코드

def solution(players, callings):
    seq = {}
    name = {}
    for i in range(len(players)):
        seq[players[i]] = i
        name[i] = players[i]

    for player in callings:
        moveto = seq[player] - 1
        loser = name[moveto]

        seq[player] = moveto
        seq[loser] = moveto + 1

        name[moveto] = player
        name[moveto + 1] = loser

    result = []
    for i in range(len(players)):
        result.append(name[i])

    return result

 

회고

 

배열값이 길어서 시간초과가 날 것 같다고 생각했음에도 배열을 선택하는 바보 같은 짓은 앞으로 하지 말자.