lv.1 달리기 경주 C#

📝 문제

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

프로그래머스

문제 설명

문자열 my_string과 이차원 정수 배열 queries가 매개변수로 주어집니다. queries의 원소는 [s, e] 형태로, my_string의 인덱스 s부터 인덱스 e까지를 뒤집으라는 의미입니다. my_string에 queries의 명령을 순서대로 처리한 후의 문자열을 return 하는 solution 함수를 작성해 주세요.

---

입출력 예

---

입출력 예 설명

4등인 "kai" 선수가 2번 추월하여 2등이 되고 앞서 3등, 2등인 "poe", "soe" 선수는 4등, 3등이 됩니다. 5등인 "mine" 선수가 2번 추월하여 4등, 3등인 "poe", "soe" 선수가 5등, 4등이 되고 경주가 끝납니다. 1등부터 배열에 담으면 ["mumu", "kai", "mine", "soe", "poe"]이 됩니다.

---

 

풀이 코드

public string[] solution3(string[] players, string[] callings)
        {
            Hashtable hash = new Hashtable();

            for (int i = 0; i < players.Length; i++)
            {
                hash.Add(players[i] , i);
            }

            for (int i = 0; i < callings.Length; i++)
            {
                // 해당 인덱스 꺼냄
                int a = (int)hash[callings[i]];

                // 저장, 스왑
                string temp = players[a];
                players[a] = players[a - 1];
                players[a - 1] = temp;

                hash.Remove(players[a]);
                hash.Remove(players[a - 1]);

                hash.Add(players[a], a);
                hash.Add(players[a - 1], a - 1);

            }

            return players;
        }

• 문제를 분석해 보면, 전형적인 스왑 알고리즘 사용해 문제를 해결해야 한다.

✍️ 중요 포인트

• 처음 구현했을 당시엔 2중 for문으로 문제를 해결하려 했으나, 2~3문제 정도 제한시간 초과로 통화하지 못하였다.
• 시간 복잡도를 생각해 보았을 때 Hashtable을 사용해 푸는 것이 맞았다.