✅ 코드
def solution(players, callings):
players_dict = {player: idx for idx, player in enumerate(players)}
for name in callings:
idx = players_dict[name]
front = players[idx - 1]
players[idx - 1], players[idx] = players[idx], players[idx - 1]
players_dict[name], players_dict[front] = idx - 1, idx
return players
입력값의 제한은 다음과 같습니다.
- 5 <= players 배열의 길이 <= 50,000
- 2 <= callings 배열의 길이 <= 1,000,000
첫 번째 풀이는 시간 초과 문제가 있었습니다.
callings 배열에 대해 반복문을 돌리고 매 시행마다 리스트의 index 함수를 사용했기 때문입니다.
시간복잡도를 계산하면 50,000 * 1,000,000으로 해당 값은 1억을 초과합니다.
따라서 시간이 초과하는 것이었습니다.
두 번째 풀이로 딕셔너리를 사용하는 풀이법을 떠올렸습니다.
딕셔너리에서 특정한 값을 검색하는 데 소요되는 시간복잡도는 O(1)입니다.
이는 index 함수를 사용한 경우보다 훨씬 빠른 수치입니다.
players 배열에 있는 각 선수들의 이름을 딕셔너리의 키로, 각 선수들의 인덱스 값을 딕셔너리의 값으로 설정하기 위해 enumerate 함수와 딕셔너리 컴프리헨션을 사용했습니다.
'알고리즘' 카테고리의 다른 글
[파이썬]프로그래머스 Lv.1 완주하지못한선수 (0) | 2023.06.03 |
---|---|
[파이썬]프로그래머스 Lv.1 다트게임 (0) | 2023.06.02 |
[파이썬]프로그래머스 Lv.1 소수만들기 (0) | 2023.06.02 |
[파이썬]프로그래머스 Lv.1 같은숫자는싫어 (0) | 2023.06.01 |
[파이썬]프로그래머스 Lv.1 추억점수 (0) | 2023.05.30 |