프로그래머스 - 달리기 경주 풀이(Python)

안녕하세요, Will 입니다.

 

오늘은 프로그래머스 연습문제 중 '달리기 경주' 문제 풀이를 가지고 왔습니다.

 

난도가 높은 문제로 보이지 않았는데 막상 풀어보니 시간초과가 발생하여 애를 좀 먹었습니다.

 

시간복잡도와 Big-O 표기법과도 연관이 있는 문제이며,

 

개념을 정리해두기 위해 블로그에 남기게 되었습니다.

 

 

결론부터 말씀드리면 검색 시에 Dictionary를 활용하면 for문, list의 index() 함수를 이용할 때보다

 

시간복잡도를 낮출 수 있으며, 검색 시간을 대폭 감소 시킬 수 있습니다.

 

 

문제

 

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

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

 

players: ["mumu", "soe", "poe", "kai", "mine"]
callings: ["kai", "kai", "mine", "mine"]

result: ["mumu", "kai", "mine", "soe", "poe"]

 

입출력 예 설명

4등인 "kai" 선수가 2번 추월하여 2등이 되고 앞서 3등, 2등인 "poe", "soe" 선수는 4등, 3등이 됩니다. 5등인 "mine" 선수가 2번 추월하여 4등, 3등인 "poe", "soe" 선수가 5등, 4등이 되고 경주가 끝납니다. 1등부터 배열에 담으면 ["mumu", "kai", "mine", "soe", "poe"]이 됩니다.

 

 

풀이

 

문제 자체는 어렵지 않다.

 

callings에 나온 이름의 선수가 바로 앞 선수를 제쳤다는 것이며,

 

players 내 선수의 위치를 등수에 맞게 고쳐주면 된다.

 

 

코딩 관점으론

 

calling list에서 값(이름)을 차례로 가져와서 players 내에 동일한 이름의 player를 찾고,

 

해당 player를 바로 앞 player와 교환해주면 될 것 같았다.

 

 

 

for문 및 List.index()를 이용하여 검색 하였을 때

 

 

문제는 list로 문제를 풀었을 때, 검색 시간이 오래 걸려 Test에 실패하였다.

 

 

시간 초과로 Test에 실패한 모습

 

 

 

처음 문제를 풀 때 아래와 같은 코드로 시도하였다.

 

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

 

위 코드는 for 문을 통해 callings의 값을 가져와(x)

 

List의 index 함수를 이용하여 x와 같은 값이 players 내부에 있는지 확인한다. // index = players.index(x)

 

그런데 x와 같은 값이 players 초반 부에 있을 수도 있으나 마지막에 있을 수도 있으며

 

따라서 최대 players의 length 만큼 검색을 수행한다.

 

따라서 callings의 length를 M, players의 length를 N으로 한다면

 

검색에 필요한 시간복잡도는 O(NM)이 된다.

 

혹시 Big-O 표기법, 시간복잡도에 대해 처음 보신 분은 아래 사이트를 통해 확인해주시길 바랍니다.

 

정리가 아주 잘 되어 있습니다.

https://blog.naver.com/kks227/220769859177

빅오 표기법(Big-O notation), 시간복잡도, 공간복잡도

 

따라서 검색 시간이 오래 걸린 것이고, 시간 초과로 테스트에 통과하지 못한 것이다. 

 

출제 의도에 이중 for문, for문 내 index() 사용 등과 같은 O(NM)은 통과하지 못하도록

 

테스트 케이스를 만들어 둔 것으로 보였다.

 

 

Dictionary를 활용하여 검색 시간 줄이기

 

자 이제 아래 코드를 보자.

 

아래 코드는 dictionary를 이용하여 검색할 수 있도록 구성하였다.

 

def solution(players, callings):
    
    hashmap = dict()
    for i,v in enumerate(players):
        hashmap[v] = i
    for name in callings:
        front, back = hashmap[name]-1, hashmap[name]
        #hashmap 내 순서 변경
        hashmap[players[front]], hashmap[players[back]] = back, front
        #list 내 순서 변경
        players[front], players[back] = players[back], players[front]
    
    return players

 

 

먼저 hashmap이라는 dictionary를 만들고, 해당 dic에 players의 player와 index를 Key, Value 형태로 담아두었다.

 

따라서 callings에서 가져온 name으로 player를 찾을 때 players 전체를 검색하지 않아도 되어,

 

1중 for문 만으로 코드가 완성되었다.

 

즉 O(NM) -> O(N) 형태로 차수를 낮추게 되어, 검색 시간을 대폭 줄일 수 있었다.

 

 

느낀 점

 

알고리즘 문제를 처음 풀 때는 Big-O니, 시간복잡도니 전혀 신경을 쓰지 않았다.

 

그런데 위 사항을 고려하지 않으면 절대 풀리지 않는 문제가 슬슬 나오고 있어 한번 정리할 필요를 느꼈다.

 

이번에 블로그에 정리하며 개념이 어느정도 잡힌 느낌이 든다.