[코딩테스트] 프로그래머스 LV.1 달리기 경주

 

 

📌문제

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

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

 

▶카테고리

5 ≤ players의 길이 ≤ 50,000
players[i]는 i번째 선수의 이름을 의미합니다.
players의 원소들은 알파벳 소문자로만 이루어져 있습니다.
players에는 중복된 값이 들어가 있지 않습니다.
3 ≤ players[i]의 길이 ≤ 10
2 ≤ callings의 길이 ≤ 1,000,000
callings는 players의 원소들로만 이루어져 있습니다.
경주 진행중 1등인 선수의 이름은 불리지 않습니다.

 

▶입출력 예

 

 

 

📌첫 번째 실패 - pop/insert

def solution(players, callings):
    
    for i in range(len(callings)):
        for j in range(len(players)):
            if callings[i] == players[j]:
                num = j
                players.pop(j)
                players.insert(num-1,callings[i])

                #print(callings[i],"현재 달리는 순서",num+1)
                #print(players)

    answer = players
            
    return answer

더 최적화해서 하는 방법 뭔데.. 

내 머리로는 삭제하고 다시 넣는 방법뿐인데..

 

 

📌두 번째 실패 - list swap

def solution(players, callings):
    
    for i in range(len(callings)):
        for j in range(len(players)):
            if callings[i] == players[j]:
                #num = j
                # players.pop(j)
                # players.insert(num-1,callings[i])
                players[j], players[j-1] = players[j-1], players[j]

                # print(callings[i],"현재 달리는 순서",num+1)
                # print(players)

    answer = players
            
    return answer

시간초과

 

📌세 번째 실패 - list swap

def solution(players, callings):
    
    for i in callings:
        num = players.index(i)
        players[num], players[num-1] = players[num-1], players[num]


    answer = players
            
    return answer

생각해보니까 for문을 두 번이나 돌릴 필요가 없었던것 ..

나 바보냐?ㅋㅋ

근데 또 시간초과임 ;;; 나 얼마나 멍청이인것일까

 

시간 초과 이유:

callings 배열(크기:M)과 players 배열(크기:N)의 크기에 비례하기 때문에 시간복잡도는 둘의 곱인 O(MN)이 되어 이 방법으로 풀 수 없습니다. 일반적으로 O(n)에서 n의 값이 1억을 넘으면 통과가 어렵다고 보면 되는데, 문제 조건을 보면 백만*5만=5백억이라는 수가 나오죠. 이 문제는 양방향 인덱싱을 이용해야 하고, 그러기 위해선 딕셔너리 두 개 또는 딕셔너리 하나와 리스트 하나가 필요합니다.

-> dict로 key, value 사용

 

📌정답- hash map

 

def solution(players, callings):
    
    dictionary = {v: k for k, v in enumerate(players)}
    #{'mumu': 0, 'soe': 1, 'poe': 2, 'kai': 3, 'mine': 4}

    for i in callings:
        num=dictionary[i]   #calling 선수의 달리는 순서
        #print(i,num)
        dictionary[players[num]] = num-1
        dictionary[players[num-1]] = num
        players[num], players[num-1] = players[num-1], players[num]

    return players

 

dictionary를 사용해 풀어야한다는 힌트를 보고 풀었다.

시간 복잡도를 줄이기 위해 인덱싱을 해서 딕셔너리의 키값으로 가져와 swap을 했다.

 

내가 생각하건데 2번째 시도에서 num = players.index(i)에서 위에 말했듯 players의 리스트와 callings리스트의 둘의 시간 복잡성이 곱해져 타임 아웃이 생긴 것이고.

players를 dictionary로 만드므로 key,value로 빠르게 찾을 수 있어 swap하면 되기때문에 시간을 단축할 수 있었다고 생각한다