20231226_달리기 경주(프로그래머스)

오늘의 TIL은 프로그래머스에 있는 달리기 경주 문제에 대한 내용이다.

 

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

프로그래머스

 

이 문제의 경우, 설명이 어렵게도 들릴 수 있지만 간단히 정리하면

 

1. players에 현재의 등수로 선수들이 있다.

2. callings에 들어있는 순서대로 해당하는 선수를 한 순위 올려준다.

즉, callings에 있는 원소들을 앞의 것과 swap해준다.

3. 최종 순위를 return한다.

 

주의점

5 <= players.Length <= 50,000

2 <= callings.Length <= 1,000,000

players는 중복된 값이 없다

callings에는 그 시점의 1등인 선수의 이름은 없다.

 

정도로 정리할 수 있는데, 우선 정답인 코드를 적으면 아래와 같다.

정답 코드

static void Main(string[] args)
{
    string[] players = { "mumu", "soe", "poe", "kai", "mine" };
    string[] callings = { "kai", "kai", "mine", "mine" };
    string[] answer = new string[] { };

    // 정답 = mumu, kai, mine, soe, poe

    Dictionary<string, int> index = new Dictionary<string, int>();

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

    for (int i = 0; i < callings.Length; i++)
    {
        Overtake(players, index, callings[i]);
    }

    answer = players;

    foreach (string player in answer)
    {
        Console.WriteLine(player);
    }
}

static void Overtake(string[] players, Dictionary<string, int> dictionary, string value)
{
    int idx1 = dictionary[value];
    int idx2 = idx1 - 1;

    string tmp = players[idx1];
    players[idx1] = players[idx2];
    players[idx2] = tmp;

    dictionary[players[idx1]] = idx1;
    dictionary[players[idx2]] = idx2;
}

이 문제를 해결하는데 사용한 방법은 저번에 공부했었던 dictionary를 사용한 것인데,

 

dictionary를 사용하지 않고 IndexOf를 사용하게되면,

 

players와 callings의 최대 길이가 50,000과 1,000,000으로 길이가 길어져 런타임 오류가 난다(9 ~ 13번 문제).

 

따라서 처음에 사용했던 방법(Overtake 함수 부분)이 아래와 같은데 위처럼 변경해야됬다.

 

static void Overtake(string[] players, string callings, string value)
{
    int idx1 = callings.IndexOf(value);
    int idx2 = idx1 - 1;

    string tmp = players[idx1];
    players[idx1] = players[idx2];
    players[idx2] = tmp;
}

 

 

문제를 해결하는데 있어서 간단하지만 핵심이 되는 부분은

string[] callings = { "kai", "kai", "mine", "mine" };

for (int i = 0; i < callings.Length; i++)
{
    // callings[i]에 있는 값을 가지고 
    // players[callings[i]]와 players[callings[i] - 1]과
    // 위치를 변경해주는 것.
}

 

이 for 안에 들어가는 players의 위치를 변경해주는 부분이 핵심이 되는데,

이 부분이 길어질 것으로 생각되고, 수정이 많이 필요할 것으로 생각하여

추월하다는 뜻으로 Overtake 함수를 만들어서 사용하였는데,

 

static void Overtake(string[] players, Dictionary<string, int> dictionary, string value)
{

}

 

위 처럼 만듦으로써 순서를 변경할 배열을 넣고, dictionary와 값(value)를 넣어줌으로써,

players 배열에 있는 값들의 위치를 변경해주는 함수를 만들 수 있었다.

처음 C#을 공부할 때는 이렇게 함수의 괄호 안쪽에 어떠한 것을 넣는 것이 막연하고 복잡하게 느껴졌었는데,

공부를 시작한지 약 2달 정도가 지나자 이러한 함수를 만드는 것도 자유롭게 가능해지고,

알고리즘 문제들도 어느정도 풀 수 있게 실력이 향상된 것을 느낄 수 있었다.

 

 

오늘은 조금 여유가 있어서 추가로 배열 비교하기라는 문제도 풀었는데,

 

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

프로그래머스

 

정답 코드

 

using System;

public class Solution {
    public int solution(int[] arr1, int[] arr2) {
        int answer = 0;
        
        if (arr1.Length == arr2.Length)
            InnerCheck(arr1, arr2, ref answer);
        else
            LengthCheck(arr1.Length, arr2.Length, ref answer);
        
        return answer;
    }
    
    static void LengthCheck(int A, int B, ref int answer)
    {
        if (A > B)
            answer = 1;
        else if (A < B)
            answer = -1;
    }
    
    static void InnerCheck(int[] arr1, int[] arr2, ref int answer)
    {
        int tmp1 = 0;
        int tmp2 = 0;
        for (int i = 0; i < arr1.Length; i++)
        {
            tmp1 += arr1[i];
        }
        for (int i = 0; i < arr2.Length; i++)
        {
            tmp2 += arr2[i];
        }
        
        if (tmp1 > tmp2)
            answer = 1;
        else if (tmp1 == tmp2)
            answer = 0;
        else
            answer = -1;
    }
}

 

이 문제를 푸는 과정에서도 Main 함수라고 할 수 있는 solution 함수에는 복잡하지 않게 함수들을 사용하게 코딩했다.

특히 answer의 값을 가져온 후에 변경해서 return해야 하므로, 함수들을 (... , ref int answer)로 만들었다.

이러한 작업들이 가능해진 것을 느낄 수 있는 하루였다.