[BOJ][C#] 5052 전화번호 목록

📕 문제

📌 링크

📗 접근

• 접두사 관계 여부 판단 문제
• 전화번호 목록을 사전순 정렬하면 접두사 관계는 인접한 두 문자열에서만 발생
• phones[i+1].StartsWith(phones[i])가 참이면 불일치( NO )

복잡도: 정렬 O(N log N) + 인접 검증 O(N·L)

📘 코드

using System;
using System.Collections.Generic;
using System.IO;
using System.Text;

public class BOJ
{
    // https://www.acmicpc.net/problem/5052

    public static void Main()
    {
        using var sr = new StreamReader(new BufferedStream(Console.OpenStandardInput()));
        using var sw = new StreamWriter(new BufferedStream(Console.OpenStandardOutput()));

        StringBuilder sb = new StringBuilder();
        int T = int.Parse(sr.ReadLine());
        while (T-- > 0)
        {
            int N = int.Parse(sr.ReadLine());
            List<string> phones = new List<string>();
            for (int i = 0; i < N; i++)
            {
                string phone = sr.ReadLine();
                phones.Add(phone);
            }

            phones.Sort();

            bool isConsistent = true;
            for (int i = 0; i < N - 1; i++)
            {
                if (phones[i + 1].StartsWith(phones[i]))
                {
                    isConsistent = false;
                    break;
                }
            }

            sb.AppendLine(isConsistent ? "YES" : "NO");
        }

        sw.WriteLine(sb.ToString());
    }
}

📒 알고리즘 분류

• 자료 구조
• 문자열
• 정렬
• 트리
• 집합과 맵
• 트라이

📙 오답노트

• 실수.. 다 출력을 깜빡하고 제출해버렸다..