[c#]백준 알고리즘 1181 - 단어 정렬(sort 사용법)

이번 알고리즘을 풀면서 정렬에 대한 이해도가 조금 올라갔다. 사실 이미 .net에서 sort()라고 배열 정렬 메서드를 제공해주고 있다. 그래서 sort()사용법을 조금 더 깊게 알아보았다. 내가 스스로 알고리즘을 사용하는것도 좋지만 매번 내가 알고리즘을 작성하는 것보다 제공되는 메서드를 잘 사용하는게 더 효율적이라고 생각된다.

---

문제

알파벳 소문자로 이루어진 N개의 단어가 들어오면 아래와 같은 조건에 따라 정렬하는 프로그램을 작성하시오.
1. 길이가 짧은 것부터
2. 길이가 같으면 사전 순으로
단, 중복된 단어는 하나만 남기고 제거해야 한다.

입력

첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다.

출력

조건에 따라 정렬하여 단어들을 출력한다.

문제풀이

이전에 sort()매서드를 사용했던 경험이 있어서 그냥 sort()매서드를 사용하면 바로 해결될거라 생각했다.

실패 코드

static void Swap(ref string a, ref string b)
{
    string swap = a;
    a = b;
    b = swap;
}

int test_case = Int32.Parse(Console.ReadLine());
string[] words = new string[test_case];

for (int i = 0; i < words.Length; i++)
{
    words[i] = Console.ReadLine();
}

Array.Sort(words);

foreach (string word in words)
{
    Console.WriteLine(word);
}

결과

하지만 위에 보이는 결과처럼 글자 순서대로 처리가 되지 않았고 중복 값도 사라지지 않았다. 이를 통해 sort()는 글자수가 아니라 글자 값을 우선순위를 두고 정렬하는 것을 볼 수있다.

먼저 아래 코드를 추가해 글자의 중복을 없애 주었다.

string[] new_arr = words.Distinct().ToArray();

words.Distinct()는 열거형으로 반환값이 나온다 그래서 ToArray()를 사용하여 배열로 바꾸었고 새로운 문자 배열에 넣어주었다.

중복 값을 없애는데 성공을 했다. 

이제 정렬을 문제의 첫번째 조건인 글자수 정렬로 바꾸어 주어야 한다.  

Array.Sort() 메서드는 기본적으로 오름차순 정렬을 수행한다. Array.Sort()를 글자수 기준 정렬의 역할을 할 수있게 바꿔줄수있는데 그 방법은 두번째 매개변수를 추가하는 것이다. 두번째 매개변수는 사용자 정의 비교함수를 작성하여 Comparison<T> 델리게이트를 사용하면 된다. 따라서 Array.Sort()코드를 아래 코드로 바꾸면 글자수 기준 정렬이 된다.

Array.Sort(words, (a, b) => a.Length.CompareTo(b.Length));

글자수 정렬과 중복값제거코드를 추가하면 아래의 결과를 얻을 수있다.

우리가  Array.Sort()를 사용자 정의 비교 함수를 사용했으므로 조건은 사용자가 정의한 비교 조건으로 변경이 된다.

우리가 원하는 조건은 글자수 정렬이후 사전순으로 정렬하는 것이다.  Array.Sort()에 조건을 2개나 사용을 하기 위해서는 생각을 조금만 더 하면 된다. 목표의 조건을 모두 만족하는   Array.Sort() 정렬 코드는 아래에 있다.

성공 코드

using System.Linq;

int test_case = Int32.Parse(Console.ReadLine());
string[] words = new string[test_case];

for (int i = 0; i < words.Length; i++)
{
    words[i] = Console.ReadLine();
}

Array.Sort(words, (a, b) =>
{
    int lengthCompare = a.Length.CompareTo(b.Length);

    if (lengthCompare == 0)
    {
        return String.Compare(a, b);
    }

    return lengthCompare;
});

string[] new_arr = words.Distinct().ToArray();

foreach (string word in new_arr)
{
    Console.WriteLine(word);
}

먼저 legthCompare에 글자수로 정렬된 우선순위를 정해준다. 만약 서로 글자수가 같을 경우 String.Compare(a, b)를 통해 오름 차순 정렬을 해준다. 결과는 당연히 성공이다.

 

심지어 Sort()는 퀵정렬로 구현되어있어 시간 복잡도는 O(nlogn)이다. 덕분에 시간제한 안에 충분히 작동된다.