백준 18870 C#) 좌표 압축

요약하자면, 주어진 숫자가 몇번째로 작은지를 출력하는 문제이다.

 

class Program
{
    static void Main()
    {
        StreamWriter sw = new(new BufferedStream(Console.OpenStandardOutput()));

        //입력
        int n = int.Parse(Console.ReadLine());
        string[] x = Console.ReadLine().Split();

        //압축된 좌표를 기존 위치에 출력하려면 기존 위치를 기억해야 하므로,
        //입력받은 x(num)를 기존 위치(oldIdx)와 함께 ValueTuple로 묶어 저장한다(input)
        (int num, int oldIdx)[] input = new (int, int)[n];

        for (int i = 0; i < n; i++)
        {
            input[i] = (int.Parse(x[i]), i);
        }

        //input을 정렬한다
        //이때 input은 num의 오름차순으로 정렬된다
        Array.Sort(input);

        //oldIdx의 순서가 뒤죽박죽이므로 출력 버퍼(output)를 통해 한번에 출력한다
        //output[oldIdx]에 newIdx를 저장한다
        //이때 newIdx는 input을 순회하면서 새로운 num이 발견될 때마다 증가한다
        int[] output = new int[n];
        int newIdx = 0;

        output[input[0].oldIdx] = newIdx;

        for (int i = 1; i < n; i++)
        {
            if (input[i - 1].num != input[i].num)
                newIdx++;

            output[input[i].oldIdx] = newIdx;
        }

        //출력
        sw.Write(string.Join(' ', output));
        sw.Close();
    }
}

 

자세한 내용은 주석으로 적어놓았다.

처음엔 Dictionary를 활용해서 풀었는데, 아무래도 n이 크다보니 좀 부담스럽기도 하고...

그래서 다른 풀이를 참고하여 C#으로 작성하였다.

 

대충 설명하자면,

입력으로 받은 x를 정렬하여 번호를 매긴다는 기저는 아마 어떤 풀이든 동일할 듯 싶은데,

이 풀이는 x를 입력 순서와 함께 묶어서 정렬하여 나중에 출력해야 하는 위치를 기억해둔다는 점이 특징이다.

물론, x를 기준으로 정렬하기 때문에 입력 순서대로 다시 출력하려면 버퍼를 활용해야 한다는 번거로움이 있다.