[코딩테스트] c# 달리기 경주

 

1. 문제 주소 (프로그래머스)

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

프로그래머스

 

2. 문제에 대한 설명

 

3. 문제 풀이

1. 실패한 코드

이 코드는 O(N^2) 시간 복잡도를 가지므로 배열 크기가 큰 경우 성능 저하를 일으킬 수 있는 코드로 실제로 돌려보면 

실패했다는 문구를 확인할 수 있다.

using System;
using System.Collections.Generic;

public class Solution {
    public string[] solution(string[] players, string[] callings) {
        HashSet<string> callingSet = new HashSet<string>(callings);

        for (int i = 0; i < players.Length; i++)
        {
            if (callingSet.Contains(players[i]))
            {
                int index = Array.IndexOf(players, players[i], 0, i);
                if (index >= 0)
                {
                    string temp = players[i];
                    players[i] = players[index];
                    players[index] = temp;
                    break;
                }
            }
        }
        return players;
    }
}

 

2. 해결한 코드

Dictionary를 사용하여 문제 해결

Dictionary는 키(Key)와 값(Value)으로 구성된 데이터 쌍을 저장하는 컬렉션!!

특정 키를 통해서 값을 검색하고 저장하는 데 유용하고, 또 해시 테이블을 기반으로 하며,

효율적인 검색 속도를 제공하기 때문에 사용하였다.

using System;
using System.Collections.Generic;

public class Solution {
    public string[] solution(string[] players, string[] callings) 
    {
    	//선수 이름, 등수
        Dictionary<string, int> playerRanking = new Dictionary<string, int>();
        for (int i = 0; i < players.Length; i++)
        {
            playerRanking[players[i]] = i + 1;
        }
        
        for (int i = 0; i < callings.Length; i++)
        {
            int callingIndex = playerRanking[callings[i]];
            
            //1등이 아닌 경우에만 교체
            if(callingIndex > 1)
            {
                string temp = players[callingIndex -2];
                players[callingIndex -2] = players[callingIndex-1]; 
                players[callingIndex-1] = temp;
             	
                //playerRanking은 등수로 정했기 때문에 위에 Players 배열과 Index를 헷갈리면X   
                playerRanking[players[callingIndex-1]] = callingIndex;
                playerRanking[players[callingIndex-2]] = callingIndex-1;
            }
        }

        return players;
    }
}