달리기 경주 (python)

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 함수를 완성해주세요.

 

제한사항

• 5 ≤ players의 길이 ≤ 50,000
• 2 ≤ callings의 길이 ≤ 1,000,000

---

코드

# Lv.1
# 달리기 경주

def solution(players, callings):
    players_dic = {} # key: 선수, value: 등수
    scores_dic = {} # key: 등수, value: 선수
    for i in range(len(players)):
        players_dic[players[i]] = i
        scores_dic[i] = players[i]
    # print(players_dic)
    # print(scores_dic)
    for calling in callings:
        now = players_dic[calling]
        # 순위에 따른 선수 수정
        scores_dic[now] = scores_dic[now - 1]
        scores_dic[now - 1] = calling
        # 선수의 등수 수정
        players_dic[calling] -= 1
        players_dic[scores_dic[now]] += 1
        # print(players_dic)
        # print(scores_dic)
    answer = list(scores_dic.values())
    return answer

 

알고리즘

1. 현재 상태를 선수와 등수를 key 혹은 value에 저장하는 players_dic, scores_dic에 저장한다(굳이 두 사전에 저장하는 이유 아래 설명 첨가)

2. callings의 한 calling마다 선수와 앞서가는 선수와 앞섬 당한 선수의 순위를 players_dic, scores_dic에서 수정한다 (now: 앞서가기 전 선수의 인덱스)

3. score에 따른 선수들의 이름을 list로 반환한다

 

피드백

처음에 배열에서 반복문을 돌면서 인덱스를 수정하는 방법을 시도했는데, 시간 초과로 통과하지 못했었다. 그러면 앞서 가는 선수가 연속으로 앞서가는 경우에 한꺼번에 계산하는 알고리즘도 고안했으나, 마찬가지로 통화하지 못했었다. queue처럼 배열을 이용하는 방법밖에 모르겠어서 다른 방법을 찾아봤고, 대부분 사전 구조를 이용하는 것을 발견했다.

 

왜 굳이 두 사전 구조를 만들 필요가 없을 것 같아 하나의 사전 구조를 이용해서 풀어봤더니 두 개의 사전이 유용함을 알겠다. 사전 구조를 이용하는 이유는 배열을 요소를 모두 확인하면 데이터가 많이 들어있을 때 시간이 많이 소요된다. 그래서 사전 구조(시간 복잡도 Q(1))를 이용하여 해당 선수의 순위를 확인하고, 순위의 선수를 바꾸는 것이다. 

 

예로 key: 선수, value: 순위 정보가 담긴 사전 구조만 이용하면 마지막에 선수를 순서대로 반환할 때 다시 정렬해서 리스트를 만들어야 한다. 반대로 key: 순위, value: 선수 정보가 담긴 사전 구조만 이용하면 앞서가는 선수의 인덱스를 찾는 데에 또 다시 배열의 요소를 훑어야 한다.

 

+ 참고 scores_dic.values는 dic_values([...])이기 때문에 list로 변환을 해줘야 통과할 수 있다.

---

시간 복잡도 참고

https://velog.io/@kimwoody/Python-%EB%A6%AC%EC%8A%A4%ED%8A%B8%EC%99%80-%EB%94%95%EC%85%94%EB%84%88%EB%A6%AC%EC%9D%98-%EC%A3%BC%EC%9A%94-%EC%97%B0%EC%82%B0-%EC%8B%9C%EA%B0%84-%EB%B3%B5%EC%9E%A1%EB%8F%84

[Python] 리스트와 딕셔너리의 주요 연산 시간 복잡도

딕셔너리 method 참고

https://hsd0937.tistory.com/20

[Python] Dictionary 예제 - Keys(), Values(), items()