달리기 경주

문제 설명

 

제한사항(문제 풀 때 players의 길이가 긴 것을 고려해야함)

 

입출력 예시 및 설명

 

풀이1

def solution(players, callings):
    answer = []
    org_list = players
    new_list = org_list.copy()
    
    for _, name in enumerate(callings):
        i = org_list.index(name)
        
        new_list[i-1] = org_list[i]
        new_list[i] =  org_list[i-1]
        
        org_list = new_list.copy()
    
    return new_list

 

채점 결과

 

제한사항에 나와있는 players의 길이가 길어서 시간초과가 나는 것 같다.

 

 

---

풀이2

def solution(players, callings):
    answer = []
    org_list = players
    new_list = org_list.copy()
    
    for _, name in enumerate(callings):
        i = org_list.index(name)
        
        new_list[i-1], new_list[i] = org_list[i], org_list[i-1]
        
        org_list = new_list.copy()
    
    return new_list

 

채점결과

코드를 수정하니까 조금 빨라진듯. 동시에 집어넣는 게 조금 더 빠르구나.

---

index는 해당값을 찾기위해 list를 순회합니다. index의 사용을 줄여보세요

 

index 를 안 쓰고 찾는 방법을 고민하다가 dict 형태에서 key로 value를 찾고 value에 1을 더해주면 된다고 생각했는데, 그럼 그 앞에 달리고 있던 애는 value에 1을 빼줘야함. 이걸 어떻게 구현해야할지 모르겠어서 일단 .. 고민 좀 더 해보자.

 

index의 시간복잡도는 index를 얻고자 하는 원소가 있는 list길이만큼. 

따라서, O(n) 이다. 여기서는 players의 길이가 최대 50,000. 

50,000정도면 몇 초 걸리려나?

 

앞으로 index를 사용할 때 시간초과가 생긴다? 그럼 dict로 풀기

dict 형태에서는 key로 value를 바로 뽑을 수 있음. -> 시간복잡도 몇? O(1)인가? len(list)처럼?

 

풀이3

def solution(players, callings):
    answer = []
    org_dict = {} 
    reverse_dict = {}
    
    for i, name in enumerate(players):
        org_dict[name] = i
        reverse_dict[i] = name
    # print(org_dict) # {'mumu': 0, 'soe': 1, 'poe': 2, 'kai': 3, 'mine': 4}
    # print(reverse_dict) # {0: 'mumu', 1: 'soe', 2: 'poe', 3: 'kai', 4: 'mine'}
    
    for i, name in enumerate(callings):
        rank = org_dict[name] # org_dict['kai']는 3
        org_dict[name] = rank - 1 # kai 순위 바꿔주기 (3등 -> 2등)
        
        new_name = reverse_dict[rank - 1] # 원래 2등이었던 사람을 찾기
        reverse_dict[rank - 1], reverse_dict[rank] = name, new_name # 2등과 3등 사람 이름 바꿔주기
        org_dict[new_name] = rank # 현재 3등이 된 사람의 등수를 3등으로 바꿔주기(2등 -> 3등)
    answer = [n for n in reverse_dict.values()]
    return answer

오예 !

---

다른 사람 풀이

def solution(players, callings):
    pla_dic = {key: i for i, key in enumerate(players)}

    for p in callings:
        c = pla_dic[p]
        pla_dic[p] -= 1
        pla_dic[players[c-1]] += 1
        players[c-1], players[c] = players[c], players[c-1]

    return players

 

딕셔너리 2개를 안 쓰고 players를 이용.

등수(숫자) 업데이트는 딕셔너리에 하고, 그 등수에 따른 이름은 players list에 업데이트.

참.... 잘 푼다.... 멋찌다..