[Programmers/Lv. 1] 달리기 경주 (프로그래머스 연습문제, Python)

📎 링크

---

프로그래머스

 

 

🤔 문제설명, 제한사항, 입출력 예

---

달리기 경주가 열렸다.
해설진들은 선수가 앞의 선수를 추월하면, 추월한 선수의 이름을 부른다고 한다.
현재 등수대로 선수들의 이름이 담긴 문자열 배열 players와 해설진이 추월할 때 부르는 선수들의 이름이 담긴 문자열 배열 callings가 주어진다고 할 때, 경주가 끝났을 때의 등수를 배열에 담아 구하라는 문제다.

 

 

🤔 내가 생각한 풀이 과정 (1) - 시간 초과 코드

---

파이썬의 swap 기능을 묻는 문제인 것 같았다.
어렴풋이, temp라는 변수를 이용해야 하는 다른 언어들과 다르게, 파이썬의 장점으로 동시 할당이 가능하다는 것을 배운 기억이 났다.

callings를 반복하면서, players에 있는 위치의 인덱스를 찾아 바로 앞에 있는 인덱스와 swap을 해주는 코드를 생각했다.

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

 

또잉.. 이 방법이 아닌 듯하다.
처음 겪어보는 시간 초과 문제를 어떻게 해결해야 하지 하고 고민에 빠지게 된다. 

 

 

🤔 내가 생각한 풀이 과정 (2) - 시간 초과 코드

---

Destructure Swap과 temp 변수를 사용한 Swap의 차이

혹시나 파이썬의 동시 할당이 일반 swap을 사용할 때에 비해서 시간을 많이 잡아먹는 것은 아닐지 고민했다.
그래서 temp 변수를 이용해서 작성해 봤는데, 크게 달라진 점은 없었다.

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

 

 

🤔 내가 생각한 풀이 과정 (3) - 성공 코드

---

가만히 코드를 살펴보니, 나도 모르는 중첩 반복문이 숨어있다는 것을 발견했다.
바로, index() 녀석.
index()라는 함수에 가려져있었을 뿐, 얘도 결국 인덱스를 찾기 위해서 내부에서 또 다른 반복을 돌리고 있었던 것이다.

이번에는 enumerate와 딕셔너리를 이용해서, index() 함수를 사용하지 않고 코드르 작성했다.

players의 값을 Key로, players의 인덱스 값을 Value로 설정한 index_dic 딕셔너리를 만들어 주고,
callings를 반복하면서 나오는 값을 index_dic의 Key 값으로 찾아, index_dic의 Value, 즉 실제 인덱스 값을 수정해 준 후 swap 하는 방식으로 코드를 구성했다.

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

    for pl in callings:
        index = index_dic[pl]
        index_dic[pl] -= 1
        index_dic[players[index-1]] += 1
        players[index-1], players[index] = players[index], players[index-1]

    return players

확실히 시간 복잡도가 개선된 것을 확인할 수 있다!