[프로그래머스][PYTHON] Lv. 1 달리기 경주

문제 설명

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

프로그래머스

 

처음에 풀었을 때는 밑에 코드와 같이 풀었다. 굉장히 간단하게 풀어졌고, 테스트 케이스도 모두 통과해서 쉬운 문제인 줄 알았다. 

def solution(players, callings):

    for call in callings:   # 불리는 선수들 순회
        callIdx = players.index(call) # 불린 선수들의 Index 저장
        
        # 불린 선수들이 앞 선수를 추월
        players[callIdx], players[callIdx-1] = players[callIdx-1], players[callIdx]
        
    return players

 

그러나 제출을 하려했더니 시간초과가 났다!!

그래서 '질문하기'를 확인해서 왜 시간초과가 났는지 찾아보았다. 

찾아보니 다른 사람들도 많이 시간초과가 나는걸 확인할 수 있었다. 

 

위의 댓글을 보고 제한사항을 확인했다. 

리스트에서 순회를 통해 인덱스를 찾아내는 것은 시간이 매우 많이 걸린다는 것을 알았다. 

이를 바탕으로  + 다른 사람들의 코드를 조금 참고하여 푼 풀이는 아래와 같다. 

 

정답 코드

def solution(players, callings):
    
    dic = {player: i for i, player in enumerate(players)} # 선수: 등수
    for call in callings:   # 불리는 선수들 순회
        idx = dic[call]     # idx는 현재 불린 선수 인덱스

        dic[call] -= 1      # 불린 선수 인덱스 변경(순위 앞으로)
        dic[players[idx-1]] += 1     # 앞 선수가 뒤로 추월(순위 뒤로)
        
        players[idx], players[idx-1] = players[idx-1], players[idx] # 순서 변경
        
    return players

 

선수와 등수를 나타내는 딕셔너리(dic)을 하나 만들어, 

선수와 등수 정보는 모두 딕셔너리를 통해 접근하고, 

player 배열에서는 직접적으로 접근하지 않고, 추월했을 시에만 정보를 변경한다. 

 

 

 

사실 아직도 딕셔너리를 왜 만들어야하는지 와닿지 않는다. 

그래도 딕셔너리를 통해 접근하는 것이 시간초과를 방지할 수 있다니, 

앞으로 저런 방법도 자주 사용해봐야겠다. 

 

 

헷갈리는 부분

def solution(players, callings):
    
    dic = {player: i for i, player in enumerate(players)} # 선수: 등수
    for call in callings:   # 불리는 선수들 순회
        idx = dic[call]     # idx는 현재 불린 선수 인덱스
        # players[idx], players[idx-1] = players[idx-1], players[idx] # 순서 변경
        
        dic[call] -= 1      # 불린 선수 인덱스 변경(순위 앞으로)
        dic[players[idx-1]] += 1     # 앞 선수가 뒤로 추월(순위 뒤로)
        
        players[idx], players[idx-1] = players[idx-1], players[idx] # 순서 변경
        
    return players

 

선수의 순서를 먼저 변경하고 인덱스를 변경하는 것과, 인덱스를 변경하고 선수의 순서를 변경하는 것의 차이점이 헷갈렸다. 

 

1) 딕셔너리에서 앞, 뒤 선수의 인덱스 변경 -> players 배열에서 앞, 뒤 선수의 이름 변경

2) players 배열에서 앞, 뒤 선수의 이름 변경 -> 딕셔너리에서 앞, 뒤 선수의 인덱스 변경

의 차이인데..

 

만약 players[idx], players[idx-1] = players[idx-1], players[idx] 
이코드를 먼저쓰면, players[idx]에 뒷선수가 저장되게 된다. 

 

따라서 

def solution(players, callings):
    
    dic = {player: i for i, player in enumerate(players)} # 선수: 등수
    for call in callings:   # 불리는 선수들 순회
        idx = dic[call]     # idx는 현재 불린 선수 인덱스
        players[idx], players[idx-1] = players[idx-1], players[idx] # 순서 변경
        
        dic[call] -= 1      # 불린 선수 인덱스 변경(순위 앞으로)
        dic[players[idx]] += 1     # 앞 선수가 뒤로 추월(순위 뒤로)
        # idx로 해야함!
        
        # players[idx], players[idx-1] = players[idx-1], players[idx] 
    return players

 

1) player 배열에서 불린 선수와 추월한 선수 정보를 변경,

-> 딕셔너리에서 불린 선수 이름을 앞으로 이동,

그리고 불린 선수가 추월한 선수의 인덱스를 뒤로 이동. 이 때, player 배열에서 이미 추월정보가 입력되어 있으므로, 

뒷 선수(player[idx])의 정보를 변경해준다. 

def solution(players, callings):
    
    dic = {player: i for i, player in enumerate(players)} # 선수: 등수
    for call in callings:   # 불리는 선수들 순회
        idx = dic[call]     # idx는 현재 불린 선수 인덱스
        
        dic[call] -= 1      # 불린 선수 인덱스 변경(순위 앞으로)
        dic[players[idx-1]] += 1     # 앞 선수가 뒤로 추월(순위 뒤로)
        # idx로 해야함!
        
        players[idx], players[idx-1] = players[idx-1], players[idx] 
    return players

 

2) 딕셔너리에서 불린 선수의 인덱스를 앞으로 이동, 

딕셔너리에서 불린 선수가 추월한 선수의 인덱스를 뒤로 이동해준다. 

 

그 후, player 배열 자체의 선수 등수를 변경해준다. 

 

 

--> 이렇게 둘 중 하나의 코드를 사용하면 된다!

 

 

아직 좀 헷갈리긴 하지만 

끄읏-! 

다시 풀어봐야겠다.