✅ 문제

문제 바로가기

✅ 나의 풀이 과정

첫번째 시도

def solution(players, callings):
    
    for calling in callings:
        idx = players.index(calling)
        players[idx], players[idx-1] = players[idx-1], players[idx]
    
    return players

시간초과로 실패하였다. 이유를 모르겠어서 질문게시판을 통해 힌트를 얻었다.

.index()의 시간 복잡도는 O(n)이다

이때 n은 리스트의 길이이다. 이 메서드는 리스트의 첫 번째 요소부터 시작하여 원하는 값을 찾을 때까지 순차적으로 비교하기 때문에, 최악의 경우 리스트의 모든 요소를 확인해야 한다.

따라서 최악의 경우 players의 길이가 50,000 , callings의 길이가 1,000,000 이므로 50,000 * 1,000,000 = 50,000,000,000 번의 연산이 필요하다.

두번째 시도

실행횟수를 줄여야 한다는 생각으로, Counter()를 떠올렸다. 플레이어의 추월 횟수를 계산하여 한번에 적용시키고자 하였다.

callings = ["kai", "kai", "mine", "mine"]

callings_counter = {"kai": 2, "mine": 2}

for idx, (key, value) in enumerate(callings_counter.items()):
	key를 value만큼 앞으로 이동시킨다. 

하지만, 최악의 경우(모든 플레이어의 이름이 한번씩 불리는 경우) callings_counter의 길이는 50,000이 된다. 플레이어의 위치를 이동하기 위해 또 index()를 사용하게되고 이경우 50,000 * 50,000 = 2500,000,000 번의 연산이 필요하다.

마지막 시도

두번의 시도를 통해 index()를 사용하지 않고 구현해야함을 깨달았다. 이때 떠올린것이 딕셔너리로 인덱스값을 저장하는 것이다.
파이썬 딕셔너리(Dictionary)는 해시 테이블(Hash Table)을 기반으로 구현되어 있어 대부분의 연산이 평균적으로 상수 시간 O(1)의 시간 복잡도를 가진다.

✅ 나의 코드

def solution(players, callings):
    # players를 딕셔너리로 변경 {이름: 인덱스}
    dic = {}
    for idx, player in enumerate(players):
        dic[player] = idx
    
    # callings 한 명씩 처리 (앞뒤 자리 이동)
    for calling in callings:
        idx = dic[calling]

        # 바뀐 players 인덱스 dic에 반영해줘야함.
        dic[calling] -= 1
        dic[players[idx-1]] += 1 

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

개선가능한 부분

# BEFORE
dic = {}
for idx, player in enumerate(players):
    dic[player] = idx

# AFTER
dic = {player: idx for idx, player in enumerate(players)}

배운점

그동안 index()를 쓰면서 시간복잡도는 고려하지 않았는데 이 문제를 통해 알고리즘문제에서 시간복잡도를 고려하는것의 중요성을 깨달았다.