프로그래머스 LV1 달리기 경주

 

문제

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

프로그래머스

 

 

 

풀이

첨에 2가지 생각을 생각했다. 2개의 리스트를 만든 다음에 서로 스왑 해서 바꾸는 형식 하고과 dict 형태로 name : 등수 을 만든 다음에 처리하는 방식이다.

 

사실 시간 복잡도 최소로 하는 방법이 dict형을 이용하여 비교하며 처리하는 방법인 것은 알고 있었으나, 그냥 호기심으로 List로 스왑 하는 방법을 먼저 시도를 하였다. 

 

2개의 리스트를 만든 다음에 각 등수를 스왑 하는 형식으로 문제를 풀었다. 

 

🖥️ main.py

from typing import List

def solution(players, callings) -> List[str]:
    
    for calling in callings:
        
        player1_name:str = calling
        player2_name:str = players[players.index(calling) - 1]
        
        player1_index:int = players.index(player1_name)
        player2_index:int = players.index(player2_name)
        
        players[player1_index] = player2_name
        players[player2_index] = player1_name
        
    return players

 

케이스 8 ~ 13 오류

 

하지만 테스트 케이스 8 ~ 13번까지 오류가 났다. index()로 접근하는 시간이 N이니까 적어도 O(N^2)보다는 아래여야겠구나 라는 생각을 했다. 따라서 두 번째 방법인 dict형을 나타내어 문제를 풀었다. 

 

일단 시간 복잡도가 O(N^2)이 되어선 안되므로, dict형에서 value 값에 맞는 key 값을 찾기 위해서 for문을 사용하면 안 된다. 따라서 이를 위해 player : rank라는 dict 자료형 하나와, rank: player라는 dict 자료형 하나를 가져와 비교하며 문제를

처리하였다.. 

 

🖥️ main.py

from typing import List, Dict

def solution(players: List[str], callings: List[str]) -> List[str]:
    
    players_rank_dict: Dict[str, int] = {players: rank + 1 for rank, players in enumerate(players)}
    rank_players_dict: Dict[int, str] = {rank + 1: players for rank, players in enumerate(players)}
    
    for calling in callings:
        player1_rank: int = players_rank_dict[calling]
        player1_name: str = calling
        
        player2_rank: int = players_rank_dict[rank_players_dict[player1_rank - 1]]
        player2_name: str = rank_players_dict[player2_rank]
        
        players_rank_dict[player1_name] -= 1
        players_rank_dict[player2_name] += 1
        
        rank_players_dict[player1_rank] = player2_name
        rank_players_dict[player2_rank] = player1_name
        
        
    answer:List[str] = [player for player, rank in sorted(players_rank_dict.items(), key=lambda x: x[1])]
        
    return answer