[Lv.1] K번째 수 [프로그래머스_코딩테스트] [정렬] [25분]

🔍 문제 요약

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

프로그래머스

숫자 배열 array를 주어주고 commands에 첫번째 숫자부터 두번째 숫자 자리까지 잘라내고 오름차순 정렬을 시키고 거기서 commands의 세번째 숫자 자리를 찾아서 정답 배열에 넣는 문제

🧠 나의 접근 방식과 시행착오

한 25분에서 30분 소요. 코딩 테스트를 풀어보면서 알게된 Span기능을 쓰려고 했다. 배열을 Slice 시키는데에 그게 제일 간편하고 좋아보여서가 이유긴 했다. 다만 프로그래머스에서는 몇가지 기능이 미지원되는 상태라고 한다. (C# 8부터 정식으로 다 지원이 되나 봄) 그러다 보니 몇번 컴파일 에러가 뜨긴 했다. (Span.Sort가 인식을 못했던 듯 함) 그래서 결국 ToArray로 바꾸고 Array.Sort를 사용해서 해결하긴 했다. 다만 이렇게 애매하게 되는 거 있고 안 되는게 있는 상황이라면 프로그래머스에서 문제를 풀 때는 Span은 못쓴다고 가정하고 푸는게 나을 듯도 하다.

using System;

public class Solution
{
    /// <summary>
    /// K번째수
    /// https://school.programmers.co.kr/learn/courses/30/lessons/42748
    /// </summary>
    public int[] solution(int[] array, int[,] commands)
    {
        int comLen = commands.GetLength(0);
        int[] answer = new int[comLen];
        int[] tempArray = new int[array.Length];
        
        // array에서 commands의 첫번째, 두번째까지 index로 잘라내고, 정렬 후 commands의 3번째 인덱스 값을 출력
        for (int t = 0; t < comLen; t++)
        {
            // i에서 j까지 잘라내기
            int i = commands[t, 0];
            int j = commands[t, 1];
            int k = commands[t, 2];
            int sliceLen = j - i + 1;
            array.CopyTo(tempArray, 0);
            var span = tempArray.AsSpan(i - 1, sliceLen);
            var spanArr = span.ToArray();
            // 정렬
            Array.Sort(spanArr);
            // k번째 찾기
            int kValue = spanArr[k - 1];
            answer[t] = kValue;
        }
        
        return answer;
    }
}

/// <summary>
/// C# 7.3
/// </summary>
internal class Program
{
    public static void Main(string[] args)
    {
        var sl = new Solution();
        var array = new int[] { 1, 5, 2, 6, 3, 7, 4 };
        var commands = new int[,] { { 2, 5, 3 }, { 4, 4, 1 }, { 1, 7, 3 } };
        var res = sl.solution(array, commands);

        foreach (var num in res)
        {
            Console.Write($"{num}, ");
        }
    }
}

✅ 풀이 코드

Span을 사용 안하고 푸는 방법으로 풀이를 한다. slice 배열을 반복문에서 동적할당시키고 Array.Copy, Array.Sort하는 방식으로 풀이를 정리한 것. 코드는 아무리 봐도 이게 더 깔끔하게 보이긴 한다. 추가로 Span으로 그냥 Array를 넣고 Span.Sort를 하게 되면 해당 배열 원본 자체가 정렬이 되는 것이라서 결국 이 방법을 쓰는게 베스트라고 생각되긴 한다.

for (int t = 0; t < comLen; t++)
{
    int i = commands[t, 0];
    int j = commands[t, 1];
    int k = commands[t, 2];
    int len = j - i + 1;

    int[] slice = new int[len];
    Array.Copy(array, i - 1, slice, 0, len);

    Array.Sort(slice);
    answer[t] = slice[k - 1];
}

🔄 정리

메모리를 아껴보기 위해 Span이라는 기능을 적극 사용해보려고 했으나 Sort를 하는 등의 작업을 하면 원본이 바뀐다는 것을 다시 한 번 생각할 필요가 있는 문제. 결국 원본이 바뀌지 않게 하려면 배열을 매번 동적할당한 뒤에 해당 내용으로 Copy, Sort하는 것이 베스트