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

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

프로그래머스

 

 

문제설명

 

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

 

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

 

 

 

문제 해결 방법

 

 

이문제 진짜 딕셔너리 순환을 위해서 이중 for문을 사용하지 않고, 하나의 반복문만 사용하고,

더이상의 반복문을 사용하지 않기 위해서, 딕셔너리 두개로 선수의 순위를 바로바로 바꿔주었다. 

 

 

코드 구현

 

def solution(players, callings):
    answer = []
    
    dicct={}
    dic={}
    for idx, i in enumerate(players):
        dicct[i]=idx
    
    for idx, i in enumerate(players):
        dic[idx]=i
        
    
    
    
#     print('dic', dic) # key는 숫자 
#     print('dicct', dicct) # key는 이름 
    
    for i in callings:
        value = dicct[i] # 숫자
        key = dic[value]
        
        value2 = dicct[i]-1
        key2 = dic[value2]
        
        
        dic[value] = key2
        dicct[key] = value2
        
        dic[value2] = key
        dicct[key2] = value
    
    for key, value in dic.items():
        answer.append(value)
    
    return answer

 

시간/공간 복잡도

 

최악의 경우 O(N)

 

 

최적화 및 개선

시간초과가 났다. 

딕셔너리 전체 순환을 하면 안되나보다.

딕셔너리 두개로 반복문 하나만 사용해서 문제를 풀었다. 

하나의 딕셔너리로 key를 통한 검색을 위해 도중에 key와 value를 바꿔주고자 했지만, 해당 방법을 사용하면 또 반복문을 사용해야 해서 해당 방법은 사용할 수 없었다. 

 

 

어려웠던 점

 

막상 풀고보니 전체 순환을 안할 수 있다는게 넘 신기하다.