백준 C# 1181 단어정렬

문제

주어지는 단어를 길이순서로 오름차순 정렬을 하되,

중복은 제거하고 같은 길이의 단어 내에서는 사전순으로 정렬하라

 

해결

단어를 정렬함에 있어 단어를 List에 담는다.

전체 리스트에서 절반씩 분할하여 길이를 비교한다.

 

최종적으로 나온 배열 위치 left의 특징 : 

현재 left의 위치는 무조건 이전 [left-1]보다 length가 크며, 현재 위치 [left]의 length와 같거나 작다.

 

그 특성을 이용해서 우측으로 이동하며 같은 길이일 경우 사전 순으로 정렬을 추가적으로 진행했다.

 

internal class _1181 //  단어 정렬
{
    static void Main(string[] args)
    {
        int iter = int.Parse(ReadLine());
        List<string> list = new List<string>();
        for(int i = 0; i < iter; i++)
        {
            string str = ReadLine();

            if (list.Contains(str)) continue;

            int left = 0;
            int right = list.Count;

            //left값을 기준으로 위치값 찾기
            //여기서 left는 [0]이 아닌 경우 [left-1] 보다 length가 큰 경우다.
            while (left < right)
            {
                int mid = (left + right) / 2;
                if (list[mid].Length < str.Length)
                    left = mid + 1; // 여기서 left는 무조건적으로 left-1보다 크다는 것을 알 수 있음.
                else
                    right = mid;
            }

            //같은 길이일 경우의 정렬
            while (true)
            {
                //배열의 최대치일 경우
                if (left >= list.Count) break;

                //현재 다음배열보다 길이가 작은 경우
                if (list[left].Length != str.Length) break;

                //다음 배열보다 사전적으로 큰 경우 위치 이동
                if (list[left].CompareTo(str) < 0) left++;
                else break;
            }

            //삽입.
            //left 위치에 str이 들어가고 기존 배열은 한칸씩 밀린다.
            list.Insert(left, str);
        }

        foreach (var item in list)
        {
            WriteLine(item);
        }
    }
}

 

 

 

Linq를 이용한 간단한 방법

 

            list.Distinct().OrderBy(x => x.Length).ThenBy(x =>x);

 

중복제거

길이를 기준으로 오름차순

정렬된 값을 기준으로 크기 오름차순 정렬