72. 달리기 경주

using System;

public class Solution {
    public string[] solution(string[] players, string[] callings) {
        string[] answer = new string[] {};
        return answer;
    }
}

 

그냥 아무 생각 없이

using System;
using System.Linq;
using System.Collections.Generic;

public class Solution {
    public string[] solution(string[] players, string[] callings) 
    {
        List<string> list = players.ToList();
        for(int i = 0; i < callings.Length; i++)
        {
            string passer = callings[i];
            int index = list.IndexOf(callings[i]);
            string overTakenPlayer = list[index - 1];
            
            list[index - 1] = passer;
            list[index] = overTakenPlayer;
        }
        return list.ToArray();
    }
}

IndexOf와 swap을 이용해서 제출했더니...

 

시간 초과가 발생했다...

 

그래서, 어떻게 하면 시간을 단축 시킬 수 있을까 고민한 결과

 

IndexOf()에서 해당 요소를 찾는 과정이 오래 걸린다 판단하여

 

Dictionary에 선수 이름을 key 값으로 하고 index를 value로 저장한 후

 

반복문을 통해 swap 시켜주는 알고리즘을 작성했다.

 

using System;
using System.Linq;
using System.Collections.Generic;

public class Solution {
    public string[] solution(string[] players, string[] callings) 
    {
        Dictionary<string,int> order = new Dictionary<string,int>();
        
        for(int i = 0; i < players.Length; i++)
        {
            order[players[i]] = i;
        }
        
        foreach(string element in callings)
        {
            int currentOrder = order[element];
            string overTakenPlayer = players[currentOrder - 1];
            
            players[currentOrder - 1] = element;
            order[element] = currentOrder - 1;
            players[currentOrder] = overTakenPlayer;
            order[overTakenPlayer] = currentOrder;
        }

        return players;
    }
}