[프로그래머스] 달리기 경주(C#)

https://school.programmers.co.kr/learn/courses/30/lessons/178871?language=csharp

프로그래머스

 

실패 코드

using System;

public class Solution {
    public string[] solution(string[] players, string[] callings) {
        string temp;
        foreach(string s in callings) {
            for(int i = 0; i < players.Length; i++) {
                
                if(players[i] == s) {
                    if(i == 0) {
                        break;
                    }
                    temp = players[i];
                    players[i] = players[i-1];
                    players[i-1] = temp;
                    break;
                }
            }
        }
        string[] answer = players;
        
        return answer;
    }
}

직관적으로 문제 자체를 그대로 코드에 옮겼다.

 

내 이름이 불렸다면? 앞 사람과 내 위치를 변경하고

만약 내가 1등이라면? break;되도록 작성했다.

 

머리를 전혀 쓰지않고 코드를 짰더니

시간 초과가 발생했다.

제한사항

제한사항을 보면 배열의 길이가 50,000, 1,000,000이다. 

 

배열의 인덱스를 찾는 것은 최악의 경우의 O(n^2)의 시간복잡도가 발생할 수 있다.

 

그래서 생각을 해봤는데, 예전에 이런 문제를 해시로 풀었던 기억이 났다.

 

성공 코드

using System;
using System.Collections.Generic;

public class Solution {
    public string[] solution(string[] players, string[] callings) {
        string[] answer = new string[players.Length];
        // HashMap
        Dictionary<string, int> dicPlayer = new Dictionary<string, int>();
        Dictionary<int, string> dicRank = new Dictionary<int, string>();
        
        // dicPlayers, dicRank 초기화
        for(int i = 0; i < players.Length; i++) {
            dicPlayer[players[i]] = i; // dicPlayers[이름 : 등수(0부터 시작)]
            dicRank[i] = players[i]; // dicRank[등수(0부터 시작) : 이름]
        }
        
        foreach(string call in callings) {
            // 만약 1등이면 순서 안바꾸고
            if(dicPlayer[call] == 0) {
                break;
            }
            
            // 1등이 아니면 앞뒤 순서 바꾸기
            int rank = dicPlayer[call]; // 이름 불린 사람의 등수
            string name = dicRank[rank];  // 이름 불린 사람의 순위
            string frontName = dicRank[rank-1]; // 앞사람의 이름
            
            dicPlayer[call] = rank - 1;
            dicRank[rank - 1] = name;
            
            int frontRank = dicPlayer[frontName];
            dicPlayer[frontName] = frontRank + 1;
            dicRank[frontRank + 1] = frontName;
        }
        
        for(int i = 0; i < players.Length; i++) {
            answer[i] = dicRank[i];
        }
        
        
        return answer;
    }
}

 

통과했다!!

 

헷.. 기분 좋다..