프로그래머스 | 달리기 경주 ⭐ - Python

🗒️ 문제

https://school.programmers.co.kr/learn/courses/30/lessons/178871

프로그래머스

 

💡아이디어

1️⃣ 첫 번째 풀이

callings를 반복해서 players와 값이 같으면 그전 값과 자리를 바꿔준다
=> 시간 초과
 

2️⃣ 두 번째 풀이

딕셔너리를 만들어서 callings 값이 나올 때마다 values 값을 -1 해준다
이때, 딕셔너리는 인데스를 사용하지 않는다는 사실을 잊지 말자!
 

✏️ 내 풀이

시간 초과 풀이

# 반복문으로 풀기 1차시도
def solution(players, callings):
    for i in range(len(callings)):
        for j in range(1, len(players)):
            if players[j] == callings[i]:
                players[idx], players[idx-1] = players[idx-1], players[idx]
    # print(players)
    answer = players
    return answer

# 반복문 2차시도
def solution(players, callings):
    for i in callings:
        idx = players.index(i)
        players[idx], players[idx-1] = players[idx-1], players[idx]
    answer = players
    return answer

 
성공한 풀이

def solution(players, callings):
	# 플레이어들의 인덱스에 따라 딕셔너리 생성
    players_dic = {player : index for index, player in enumerate(players)}
    
    # callings를 반복해서 calling에 맞추어 values 값 -1
  	## players를 key값으로 이용해야하기 때문에 꼭 players 리스트 순서 변경해주기
    for calling in callings:
        index = players_dic[calling]
        players_dic[calling] -= 1
        players_dic[players[index - 1]] += 1
        players[index-1], players[index] = players[index], players[index-1]
    
    return players

 

😊 후기

세 풀이로 시간복잡도에 대해 생각해 볼 수 있었다.
프로그래머스의 테스트케이스에서는 1-2 풀이가 시간초과가 덜 진행됐다 그러나, players.index(i)의 경우 호출할 때마다 순차검색* 순차 검색 : 처음부터 하나씩 차례대로 검색하는 알고리즘을 수행하므로 players의 크기가 매우 커지게 되면 오히려 더 성능이 저하될 수도 있다.
즉, 반복문을 이용한 1-1, 1-2 풀이는 약 O(n*m)의 시간복잡도를 가지게 되며, 마지막 풀이의 경우 O(n)의 시간복잡도를 가지게 된다.