Programmers - 달리기 경주

프로그래머스

 

문제

얀에서는 매년 달리기 경주가 열립니다. 해설진들은 선수들이 자기 바로 앞의 선수를 추월할 때 추월한 선수의 이름을 부릅니다. 예를 들어 1등부터 3등까지 "mumu", "soe", "poe" 선수들이 순서대로 달리고 있을 때, 해설진이 "soe"선수를 불렀다면 2등인 "soe" 선수가 1등인 "mumu" 선수를 추월했다는 것입니다. 즉 "soe" 선수가 1등, "mumu" 선수가 2등으로 바뀝니다.

선수들의 이름이 1등부터 현재 등수 순서대로 담긴 문자열 배열 players와 해설진이 부른 이름을 담은 문자열 배열 callings가 매개변수로 주어질 때, 경주가 끝났을 때 선수들의 이름을 1등부터 등수 순서대로 배열에 담아 return 하는 solution 함수를 완성해주세요.

 

제한사항

• 5 ≤ players의 길이 ≤ 50,000
• 2 ≤ callings의 길이 ≤ 1,000,000

 

접근방식

callings 배열안에 있는 값들을 하나씩 순회하면서 players의 calling 값을 인덱스를 calling_index 로 받아줌

그리고 그 calling 값의 앞 인덱스의 값과 교환해야 하므로 front_index를 선언

두 값을 교환하는 방식으로 풀었는데

def solution(players, callings):
    for calling in callings:
        calling_index = players.index(calling)
        front_index = players.index(calling) - 1
        # 교환
        players[calling_index], players[front_index] = players[front_index], players[calling_index]
    
    return players

다음과 같이 시간초과가 뜸

 

찾아보니 'players 배열을 사용하여 players.index(calling)와 players.index(calling) - 1을 사용하여 해설진의 호출에 따라 선수의 위치를 변경하려고 했기 때문에 시간 복잡도가 높아서 시간 초과가 발생함. players.index(calling)는 배열에서 해당 요소를 찾는 데 선형 검색을 사용하며, 이 작업을 반복 호출하는 것은 효율적이지 않음. 또한 players 배열에서 선수를 추월할 때마다 배열의 모든 요소를 이동시켜야 하는데, 이 작업은 배열의 요소를 이동하면서 많은 시간이 소요됨. 따라서 시간 복잡도를 줄이기 위해 효율적인 알고리즘을 사용해야 함. 한 가지 효율적인 방법은 players 배열을 딕셔너리로 변환하여 선수의 이름을 인덱스로 매핑하는 것' 이라는 답변을 받음

 

딕셔너리를 잘 몰라 공부해보았음

해당 게시글은 아래에 첨부

코딩테스트 준비 - 파이썬 해시 정리

 

 

 

코드

def solution(players, callings):
    # 각 선수 이름을 딕셔너리의 키로 사용하고, 그 선수의 인덱스를 해당 키에 대응하는 값으로 설정
    player_index = {player: idx for idx, player in enumerate(players)}
    for calling in callings:
        calling_index = player_index[calling]
    
        if calling_index > 0:
            # 선수의 위치를 갱신
            players[calling_index], players[calling_index - 1] = players[calling_index - 1], players[calling_index]        
            player_index[calling], player_index[[players[calling_index]]] = calling_index - 1, calling_index
    return players

코드가 짧아서 단순해보이지만 enumerate 개념을 몰랐어서 이해하는 데 시간이 좀 걸림

enumerate(players)는 players 리스트를 순회하며 각 요소와 해당 요소의 인덱스를 튜플 형태로 생성함

예로,

players 리스트가 ["mumu", "soe", "poe"]라면,

enumerate(players)는 (0, "mumu"), (1, "soe"), (2, "poe") 의 튜플을 생성함

이렇게 생성된 튜플을 기반으로 player: idx 형태의 키-값 쌍을 가지는 딕셔너리를 생성함

player_index = {'mumu': 0, 'soe': 1, 'poe': 2}

 

player는 선수의 이름이 되고, idx는 해당 선수의 인덱스가 됨

딕셔너리 컴프리헨션을 사용하면 각 튜플에서 키-값 쌍을 추출하여 딕셔너리를 생성할 수 있음

 

그리고 callings 배열을 돌면서 각 값들을 calling으로 받고 calling_index 변수에 player_index[calling]을 할당해줌

그리고 그 calling_index가 0보다 크면 선수의 위치를 갱신해줌(앞 선수와 뒷 선수를 바꾸는 과정)