[프로그래머스 level1] 달리기 경주 (실패 - 시간초과)

해설

예시 입력에 보면

['mumu', 'soe', 'poe', 'kai', 'mine']이렇게 players를 이루고 있고

불린 애들의 리스트는 callings ['kai', 'kai', 'mine', 'mine']이렇게 되어있다.

 

그러면 문제에 따라서 보면

1번째로 'kai'가 불렸으니

players는 ['mumu', 'soe', 'kai', 'poe', 'mine'] 이렇게 바뀔거고

2번째로 'kai'가 불렸으니

players는 ['mumu', 'kai', 'soe',  'poe', 'mine'] 이렇게 바뀔거고

3번째로 'mine'가 불렸으니

players는 ['mumu', 'kai', 'soe',  'mine', 'poe'] 이렇게 바뀔거고

4번째로 'mine'가 불렸으니

players는 ['mumu', 'kai', 'mine', 'soe', 'poe'] 이렇게 바뀔거다.

 

그래서 첫번째 풀이는 callings를 for문을 돌려서 불려진 애랑 그 앞에 있는 애랑 둘의 위치를 바꿔주는 로직을 짰다.

def solution(players, callings):
    for calling in callings:
        print(calling)
        i = players.index(calling)
        print(i)
        players[i-1], players[i] = players[i], players[i-1]
    return players

근데 시간 초과가 떴다..

callings이 1,000,000까지 와서 for문을 아예 쓰면 안되는 줄 알아서 삽질을 시작했다.

하지만, 아무리 생각해도 callings를 반복하지 않으면 문제를 풀 수 없는 시스템이었고. 

도무지. 내가 짠 코드에서 시간을 줄일 수 있는 방법이 생각 나지 않아서 다른 사람의 코드를 봤다..

def solution(players, callings):
    dict = {key: i for i, key in enumerate(players)}
    
    for calling in callings:
        c = dict[calling]
        dict[calling] -= 1
        dict[players[c-1]] += 1
        players[c-1], players[c] = players[c], players[c-1]
        
    return players

해설을 해보자면

제일 핵심적인 사항은 인덱스를 가지고 순서를 바꿔치기 하는 건데, 그 세부적인 사항들을 하나하나 보자면,

 

dict={key: i for i, key in enumerate(players)}

현재 players에 있는 요소를 딕셔너리(dict)로 풀어서 넣었다.

딕셔너리(dict)에 key값에는 players의 요소, value값에는 해당 players의 요소의 인덱스값을 넣었다.

{'mumu' : 0, 'soe': 1, 'poe':2, 'kai':3, 'mine':4}

이런식으로 된다.

 

for calling in callings:

이름이 불린 요소들 하나하나를 for문으로 돌려서 calling이라는 요소에 넣었다.

 

c = dict[calling]

현재 불린 애를 key값으로 dict에서 value를 찾아서 그 값을 c에 저장한다. 그러면 c는 현재 불린 애의 players의 위치(인덱스)이다.

 

dict[calling] -=1

그리고 현재 불린 애를 앞으로 보낸다. -> 인덱스 값을 1 줄인다.

 

dict[players[c-1]] += 1

근데 인덱스를 줄인 값에 어떤 수가 있으니까 그 값은 뒤로 뺀다 -> 인덱스 값을 1 늘린다.

players[c-1]은 결국 key값이니까 key값으로 value를 찾아야 해서 저렇게 했다.

 

그리고 players라는 리스트의 순서를 바꿔준다.

swap을 사용한다.

파이썬은 간단하게

players[c-1], players[c] = players[c], players[c-1]이렇게 된다.(c언어 처럼 한 변수에 저장했다 옮기지 않아도 된다.)

 

그러면 players의 순서가 정렬된다.

 

배운점

c 언어처럼 swap 안해도 된다는 걸 처음 알았고

이거 문제 한 3시간 푼거같은데, 1-2시간으로 짤라야 하는 것 같다. 도무지 못풀겠을 땐 답을 보고 푸는 방법을 배우면 된다.