[코딩테스트] 달리기

내가 처음 문제를 보고 작성한 코드 

 

using System;

public class Solution {
    public string[] solution(string[] players, string[] callings) {
        
        for (int i = 0; i < callings.Length; i++) {
            string call = callings[i];
            
            int index = Array.IndexOf(players, call);
            if (index > 0) {
                string temp = players[index - 1];
                players[index - 1] = players[index];
                players[index] = temp;
            }
        }
        
        return players;
    }
}

 

 

하지만 성능적인 측면에서 문제가 발생하여 통과하지 못한 부분들이 존재했는데 

그 이유가 바로 Array.IndexOf 이는 배열의 요소를 순차적으로 검색 후 특정 값의 인덱스를 반환하는 방식이기 때문에 

 

배열의 크기에 따라  선형 시간 복잡도를 가진다

즉 최악의 경우에는 모든 요소를 다 검사해야 하기 때문에 많은 시간이 소요된다는 것!!!!!!!!

 

그래서 생각한 방식이 Dictionary 

https://learn.microsoft.com/ko-kr/dotnet/api/system.collections.generic.dictionary-2?view=net-8.0

사이트 설명을 보면 

 

제네릭 클래스는 Dictionary<TKey,TValue> 키 집합에서 값 집합으로 매핑을 제공합니다. 사전에 추가하는 각 항목은 값과 관련 키로 이루어져 있습니다. 클래스가 해시 테이블로 구현되기 때문에 Dictionary<TKey,TValue> 해당 키를 사용하여 값을 검색하는 것은 매우 빠르며 O(1)에 가깝습니다.

 

탐색 속도가 매우 빠르다는 것을 확인할 수 있다.

 

그래서 Dictionary를 통해 각 선수들의 위치를 저장하고 인덱스를 통해 선수들의 위치를 보다 빠르게 탐색하여 

위치를 변경해주는 방식으로 재작성하였다!! 

 

using System;
using System.Collections.Generic;

public class Solution {
    public string[] solution(string[] players, string[] callings) {
       
        Dictionary<string, int> playerPositions = new Dictionary<string, int>();
        
        for (int i = 0; i < players.Length; i++) 
        {
            playerPositions[players[i]] = i;
        }

        for (int i = 0; i < callings.Length; i++) 
        {
            string call = callings[i];
            
            int index = playerPositions[call];
            if (index > 0) 
            {
                string previousPlayer = players[index - 1];
                
                players[index - 1] = call;
                players[index] = previousPlayer;
                
                playerPositions[call] = index - 1;
                playerPositions[previousPlayer] = index;
            }
        }
        
        return players;
    }
}