프로그래머스 level 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등인 선수의 이름은 불리지 않습니다.

---

입출력 예playerscallingsresult

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

["kai", "kai", "mine", "mine"]

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

---

입출력 예 설명

입출력 예 #1

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"]이 됩니다.

 

코드

from collections import Counter

def solution(players, callings):
    rank = {player: idx for idx, player in enumerate(players)}

    # {'mumu': 0, 'soe': 1, 'poe': 2, 'kai': 3, 'mine': 4}
    for calling in callings:
        idx = rank[calling]             # idx = 3
        front_player = players[idx - 1] # front_player = 2
        players[idx - 1], players[idx] = players[idx], players[idx - 1]
    
        rank[calling] -= 1
        rank[front_player] += 1
    
    return players

 

 

사실 처음에는 아래와 같이 인덱스를 사용하여 문제를 풀었다.

def solution(players, callings):
    for calling in callings:
        for i in range(len(players)):
            if players[i] == calling:
                players[i], players[i-1] = players[i-1], players[i]
                
    return players

 

그러나 테스트 케이스는 통과 했으나 실제 코드 제출 시 시간 초과로 통과하지 못했다.

인덱스는 모든 리스트에 대해서 하나씩 순차적으로 검사를 해서 시간이 많이 걸리기 때문이다. 시간 복잡도는 O(n)이다.

 

그러나 이를 딕셔너리로 바꾸게 되면 hash값을 가진 트리구조로 Key값을 저장하기 때문에 시간 복잡도가 O(1)이다.

따라서 아래와 같이 흐름을 잡고 hash로 바꿨다.

선수 이름이 불림
→ 그 선수의 현재 인덱스를 딕셔너리에서 바로 찾음
→ 바로 앞 선수와 리스트에서 swap
→ 두 선수의 인덱스를 딕셔너리에서도 갱신

우선 player의 현재 위치를 저장한다.

rank = {player: idx for idx, player in enumerate(players)}

players = ["mumu", "soe", "poe", "kai", "mine"]

 

rank = {
    "mumu": 0,
    "soe": 1,
    "poe": 2,
    "kai": 3,
    "mine": 4
}

 

 

이제 callings에서 불린 호출로 rank에서 idx를 참고하여 1명의 선수를 추월한다.

idx = rank["kai"]

그러면 `idx = 3`이고, 현재 'kai'는 player[3]에 있음을 확인할 수 있다.

 

따라서 kai 앞에 있는 front player는 player[2]이고, 'poe'임을 확인할 수 있다.

front_player = players[idx - 1] = players[2]

 

이제 그 둘의 자리를 바꾸어 추월시킨다.

players[idx - 1], players[idx] = players[idx], players[idx - 1]
# players[2], players[3] = players[3], players[2]

 

 

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

 

 

여기서 유념해야할 점은 현재 바꾼 것은 players 리스트이고, rank 딕셔너리를 변경하지 않았다는 점이다.

 

kai와 poe의 위치가 바뀌었음으로 아래와 같이 딕셔너리를 수정한다.

rank[calling] -= 1
rank[front_player] += 1

 

rank["kai"] -= 1   # 3 -> 2
rank["poe"] += 1   # 2 -> 3

 

 

이 과정을 callings 전체에 반복하면 된다.

 

 

처음 내가 생각한 방식은 매번 이름을 찾으려고 리스트를 처음부터 훑었다. 이는 한 번 찾을 때 50000번 비교할 수 있다.

for i in range(len(players)):
    if players[i] == calling:

 

 

그러나 해시 방식은 딕셔너리 조회라서 바로 찾을 수 있다.

idx = rank[calling]

 

 

소감

이런 문제를 맞닥뜨리면 가장 먼저 드는 생각은 '쉽다'이다.

그러나 막상 내가 구현하려고 하면 막막하다.. 아직 멀었다는 뜻이다

 

이번에도 또 어렵게 가려고 Counter 함수를 건드렸다 지웠다가, index 건드렸다 지웠다가 했다.

효율적으로 사고하는 방식을 키워야겠다.