[Python] 프로그래머스 lv1 - 달리기 경주

[Python] 프로그래머스 lv1 - 달리기 경주

 

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

프로그래머스

 

 

문제 설명

 

 

 

풀이 코드

 

• 첫 번째 시도코드
  • 시간초과 발생 다른 방법 필요
    • 제약 조건을 살펴보니 리스트에 한 번에 많은 데이터가 들어와서 데이터가 많아지면 list에서는 문제가 해결돼도 시간 초과가 발생한다.

def solution(players, callings):
    answer = []
    # calling 배열 반복문
    
    # 만약 해당 인물이 불렸다면, 앞의 인물과의 교환작업
    
    for i in callings:
        
        people = players.index(i)
        players[people-1], players[people] = players[people],players[people-1]
    
    return players

 

첫 번째 코드에서는 시간초과가 발생하였다. 그렇기에 다른 방법을 찾아야겠다고 생각했다. 질문하기의 답변들을 찾아보다가 dictionary를 사용하면 for loop의 횟수를 줄일 수 있다고 하여 해당 방법으로 방향을 잡았다.

 

• dictionary
  • 리스트를 사용해서 순서를 변경한다면 대상들의 index를 조회하는 과정에서 loop가 반복이 되는 상황이 발생한다. 이미 외부에서 calling을 진행하기 위한 o(n)와 index 탐색의 o(n)으로 시간 복잡도가  o(n^2)이 된다고 한다. 
  • dictionary의 경우 해당 index를 구하기 위한 loop를 돌릴 필요가 사라져서 시간 복잡도가 O(n)으로 성능이 개선이 된다.

def solution(players, callings):

    race = {} # 현재 경기의 순위 
    
    for i, p in enumerate(players):
        race[p]=i # 인원과 등수
            
    for c in callings:
        # 기존 index()를 race 딕셔너리로 사용
        # 해당 인물이 불렸다면, 앞의 인물과의 교환작업 -> if문으로 확인했었지만 문제에서 
        # players의 원소로만 이루어졌다고 말했기에 확인 작업 불필요
        idx = race[c]
        race[c] -=1
        race[players[idx-1]]+=1

        players[idx-1], players[idx] = players[idx], players[idx-1]
    
    
    return players