백준#5052 - 전화번호 목록

https://www.acmicpc.net/problem/5052

5052번: 전화번호 목록

정렬 문제로 분류된 5052번 전화번호 목록 문제 입니다.

 

 

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
 
namespace _5052
{
    class Program
    {
        static void Main(string[] args)
        {
            int testCount = int.Parse(Console.ReadLine());
            var ansList = new List<bool>();
            for(int i = 0; i < testCount; i++)
            {
                int numCount = int.Parse(Console.ReadLine());
                var list = new List<string>();
                for(int j = 0; j < numCount; j++)
                {
                    list.Add(Console.ReadLine());
                }
 
                list.Sort(new Comparer());
 
                for(int j = 0; j < list.Count; j++)
                {
                    if(j == list.Count - 1)
                    {
                        ansList.Add(true);
                        break;
                    }
                    if(list[j + 1].Contains(list[j]))
                    {
                        if(list[j + 1].Length >= list[j].Length)
                        {
                            if(list[j + 1].Substring(0, list[j].Length) == list[j])
                            {
                                ansList.Add(false);
                                break;
                            }
                        }
                    }
                }
            }
            foreach (var ans in ansList)
                Console.WriteLine(ans? "YES" : "NO");
        }
    }
 
    public class Comparer : IComparer<string>
    {
        public int Compare(string x, string y)
        {
            for(int i = 0; i < ((x.Length > y.Length)? y.Length : x.Length); i++)
            {
                if (x[i] != y[i])
                    return x[i].CompareTo(y[i]);
            }
            return x.Length.CompareTo(y.Length);
        }
    }
}
 

처음에는 트리로 접근하려 했습니다. 123이 숫자로 들어왔다면 1을 떼고 서브 트리로

23을 보내 마지막 노드에서 해당 번호는 있다 라는 것을 표시하려 했습니다.

 

트리를 딕셔너리로 구성했는데 시간 초과가 나버려서.... 단순 정렬로 풀었습니다.

 

해결 방법.

우선 정렬 방법을 정의했습니다.

두 스트링중 길이가 짧은것 만큼 각 숫자를 보게됩니다. 하나라도 다른게 있다면

i번째 숫자가 작은 것을 뒤로 보내도록 했습니다. 모두 겹치는 것이라면 길이순으로 정렬합니다.

 

ex) 1234, 1245, 12345 이렇게 있을 경우

1234, 12345, 1245 순으로 정렬되게 했습니다.

 

다음 리스트의 첫번째 string부터 다음것과 비교를 시작합니다.

현재 string보다 다음것의 길이가 길다면 다음것의 Substring을 현재것의 길이만큼 가져옵니다.

 

둘이 같다면 이는 무결성에 위배됩니다.