알고리즘 연습/집합과 맵

[Lv.1 / 프로그래머스 / 파이썬] 달리기 경주

김세진 2023. 11. 19. 20:52
반응형

 

 

 

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

 

 

 

 

 

풀이

 

 

최소한의 비용으로 players 의 위치를 탐색해 순위를 바꿔야 하는 문제이다.

단순히 callings 에 있는 이름들을 players 리스트를 순회하며 찾는다면 50,000 * 1,000,000 만큼의 비용이 발생할 것이다.

따라서 callings 에 있는 이름을 playres 에서 O(1) 만에 탐색할 수 있는 딕셔너리와 같은 HashMap 을 사용해야 한다.

 

def solution(players, callings):
    rank = dict()
    for i in range(len(players)):
        rank[players[i]] = i
    
    for name in callings:
        idx = rank[name]
        # 인덱스 변경
        rank[players[idx-1]], rank[name] = rank[name], rank[players[idx-1]]
        
        # 실제 위치 변경
        players[idx], players[idx-1], = players[idx-1], players[idx]
        
    return players

 

 

 

 

반응형