프로그래머스 - 달리기 경주 _ Python3

 주말 과제로 프로그래머스의 달리기 경주를 풀었다. 문제는 이해하고 바로 작성하기 쉬운 편이어서

떠오르는대로 금방 작성해볼 수 있었다. 그런데 시간 복잡도를 전혀 고려하지 못해 관련해서 조금 다뤄 보려고 한다. 

 

문제 요약 

 문제는 리스트 안의 요소들을 순회하며 탐색한 뒤 해당 요소들을 가지고 또 다른 리스트에 접근하여 Swap 시켜주는 문제였다. 

 

내가 짠 코드 

players = ["mumu", "soe", "poe", "kai", "mine"]
callings = ["kai", "kai", "mine", "mine"]

def solution(players, callings):
    for i in callings: 
        a = players.index(i)
        b = players.index(i)-1
        players[a], players[b] = players[b], players[a]

    return players

보기 쉽게 players와 callings 를 같이 적었다. 위 처럼 하면 10번째 쯤 테스트에서 시간 초과가 발생하며 문제를 통과하지 못한다. 처음엔 변수를 따로 만들어주고 그 변수를 가지고 인덱싱을 하는 것이 문제일 것이라 생각하고 접근했는데 해결되지 않을 뿐더러 원인이 아니었다. 

 

 원인은 for 문을 만든 뒤 그 안에서 변수 a, b 를 지정할 때 index를 한 것 때문인 것 같았다 .인덱스를 지정하는 연산의 경우에는 무조건 O(N)의 시간복잡도가 들어간다고 한다. 그래서 보통은 리스트 보다 스택이나 큐 등을 사용한다고 한다... 

 

반면 파이썬의 딕셔너리를 사용하면 어떤 메소드를 사용해도 시간복잡도가 O(1)인 것을 알 수 있다. Key와 Value값으로 접근하기 때문에 시간복잡도가 거의 O(1)이라고 한다. 

 

 아래 자료를 참고하였다. https://infinitt.tistory.com/376

(Python) 파이썬 - list, Dict의 메소드 시간복잡도

 다만 , index 메서드 자체의 시간복잡도는 O(1)인데, 왜 O(N)의 시간복잡도를 갖는다고 하는 것일까 찾아보았는데, 관련해서는 이렇게 정리 할 수 있을 것 같다. 파이썬의 기본 산술 연산들은 O(1)을 갖는데 길이기 n인 리스트를 처음부터 끝까지 요소를 하나씩 접근한다면 N번 하게 되므로 O(1) * N이어서 O(N)이라고 생각할 수 있다고 한다. 아래 글을 읽어보니 결국 어떤 함수를 사용하냐 보다는 어떤 자료형을 가지고 하는 것이 더 중요한 것 같다. List의 삽입, 제거, 탐색, 포함은 모두 O(N)의 시간복잡도를 갖는다고 한다. 딕셔너리를 사용하는 것이 좋다. 

https://chancoding.tistory.com/43

[Python] 파이썬 자료형 및 연산자의 시간 복잡도(Big-O) 총 정리

 

자주 쓰이는 문법 함께 정리 - enumerate 

 많은 프로그래밍 언어들이 인덱스 변수를 증가시키면서 for 루프를 돌린다. 하지만 파이썬에서는 대신 enumerate()라는 내장 함수를 통해 이러한 인덱스 변수 없이 루프를 돌릴 수가 있다고 한다. 

 

방법은 for문의 in 뒷 부분을 enumerate() 함수로 한 번 감싸주기만 하면 된다고 한다. enumerate()함수는 기본적으로 인덱스와 원소로 이루어진 튜플을 만들어 준다고 한다. 따라서 인덱스와 원소를 각 다른 변수에 할당하고 싶다면 인자 풀기, 즉 unpacking를 해줘야 한다. 

 

 

 

다른 사람의 코드 

def solution(players, callings):  # enumerate(리스트)
    idx = {i: players for i, player in enumerate(players)}
    p = {player: i for i, player in enumerate(players)}
    
    
    for i in callings: 
        print
        loc = p[i]   # 현재 등수, player들의 현재 등수 
        loc2 = loc -1 # 앞 등수 
        i2 = idx[loc2]  # 앞 선수 , players가 값으로 담긴 사전에 접근하여 선수 이름 출력 
        
        idx[loc] = i2   # 등수 : 선수 딕셔너리에서 현재 등수의 선수를 앞 선수로 업 
        idx[loc2] = i  # 등수 : 선수 딕셔너리에서 앞 등수의 선수를 현재 선수로 다운 
        
        p[i] = loc2 # 선수 ; 등수 딕셔너리에서  현재 선수의 등수를 앞 등수로 업 
        p[i2] = loc # 선수; 등수 딕셔너리에서 앞 선수의 등수를 현재 등수로 다운 
        
    return list(idx.values())    # 등수 : 선수 딕셔너리의 값을 출력하여 리스트로 변환

 

enumerate 와 딕셔너리를 사용하여 풀이한 것이다. 딕셔너리를 

1. 등수 : 선수 

2. 선수 : 등수 

의 형태로 두 개를 만들어서 각 딕셔너리에 인덱싱을 하는 방법으로 값의 순서와 인덱스의 순서를 바꿔주는 방법이다. enumerate를 사용하여 인덱스와 값을 추출하여 딕셔너리로 만들어주고, callings를 순회할 때 마다 딕셔너리를 수정해주는 방법으로 시간초과를 방지할 수 있다. 딕셔너리를 사용할 수 있다는 것은 좋은데, 등수를 따로 수정해 줘야 하는 작업은 조금 번거로운 것 같다. 리스트의 append를 사용하면 요소가 삽입되면서 원래 있던 요소는 알아서 뒤로 밀리는데 말이다. 

 

 그러나 이 문제의 핵심이 딕셔너리를 활용하는 것인 것 같으니 잘 알아두고 다음 번엔 딕셔너리를 활용할 수 있도록 해야겠다.