문제 및 데이터 이해

A72. 달리기 경주

(상략) 해설진들은 선수들이 자기 바로 앞의 선수를 추월할 때 추월한 선수의 이름을 부릅니다. (중략) 선수들의 이름이 1등부터 현재 등수 순서대로 담긴 문자열 배열 players와 해설진이 부른 이름을 담은 문자열 배열 callings가 매개변수로 주어질 때, 경주가 끝났을 때 선수들의 이름을 1등부터 등수 순서대로 배열에 담아 return 하는 solution 함수를 완성해주세요.

callings에서 선언되는 선수의 이름을 players에서 찾아, 그 앞의 index인 선수와 위치를 바꿔주면 된다
직관적으로 생각하면, 그냥 리스트 상태 그대로 index() 함수를 사용하고, 그 index와 1개 전 index의 player name을 변수로 가져왔다가 각각 반대로 덮어씌워주면 되는 간단한 문제.

...하지만 그렇게 간단한 문제일리가 없다

핵심 아이디어

리스트의 시간 복잡도

리스트에서 for문을 돌리는 과정은 상당한 연산량을 갖는다.
리스트는 '순서'가 존재하는 객체이고, index()와 같은 함수는 반드시 index==0인 값부터 확인하기 때문이다.
이를 '시간 복잡도'라고 하는데, 알고리즘 문제의 경우 이처럼 시간 복잡도를 고민하게 하는 문제가 많다.
파이썬 자료형 별 주요 연산자의 시간 복잡도 (Big-O)
python list 연산에 따른 시간 복잡도
심지어는, list[i]와 같은 특정 1개 index의 값을 가져오는 것조차 0번 index부터 차례로 훑어봐야지만 가능하다. 당연히 연산량이 많아질 수 밖에.

그렇다면 어떤 방법으로 시간 복잡도를 낮출 수 있을까?

순서를 갖지 않는 객체 : 딕셔너리

딕셔너리는 개념적으로 key에 매핑된 value 값을 갖는 객체이다. 여기에 순서는 존재하지 않는다.
그렇기에 특정 key를 호출하면 바로 그에 맞는 value를 반환하기에 훨씬 시간 복잡도가 낮다.

하지만 딕셔너리 또한, 딕셔너리 내에서 value를 통해 key값을 '찾도록' 지시한다면 하나씩 훑어봐야 하기 때문에 연산량이 늘어난다.
[Python] Value로 Key찾기

이를 해결하는 방법은 간단한데, {key:value}와 {value:key}인 딕셔너리를 각각 만들어서 양쪽을 동시에 변경하는 식으로 진행하는 것이다.

최종 코드

앞서 설명한 개념을 반영하여 코드를 작성하면 아래와 같다.

def solution(players, callings):
    answer = []
    player_dict = {}
    rank_dict = {}
    
    for i, player in enumerate(players):
        # player_dict = {선수 이름 : 선수 순위}
        player_dict[player] = i
        # rank_dict = {선수 순위 : 선수 이름}
        rank_dict[i] = player
        
    for call in callings:
        i = player_dict[call] # 호명된 선수 기존 순위
        name_1 = rank_dict[i] # 호명된 선수 이름
        name_2 = rank_dict[i-1] # 호명된 선수에게 추월당한 선수 이름
        
        # 선수 순위 조정
        player_dict[name_1], player_dict[name_2] = i-1, i
        
        # 순위에 따른 선수 이름 조정
        rank_dict[i], rank_dict[i-1] = name_2, name_1
    
    # 선수 순위대로 이름 호명
    for i in range(0, len(players)):
        answer.append(rank_dict[i])
    
    return answer

Appendix: 폐기된 코드

def solution(players, callings):
    answer = []
    answer = players.copy()
    
    for call in callings:
        i = answer.index(call)
        player_1, player_2 = answer[i], answer[i-1]
        answer[i], answer[i-1]  = player_2, player_1
    
    return answer

최초로 작성했던, 런타임 오류로 고통 받았던 코드