5052번:전화번호 목록(Java)

 

 

 문제에서 전화번호는 10자리 이하라고 했다. int 자료형의 범위는 -2,147,483,648 ~ 2,147,483,647 이므로 int 자료형을 쓰면 모든 전화번호를 저장할 수 없으므로 String 배열을 전화번호부로 사용했다.

 

 

 전화번호를 입력받고 Arrays.sort()로 오름차순으로 정렬한 후, startsWith 함수로 현재 index + 1 번째 문자열이 현재 index를 포함하는지 검사한 후 출력했다. 오름차순으로 정렬되어 있으므로 +1 번째만 검사하면 된다. 이렇게 하면 시간복잡도를 O(n^2)으로 줄일 수 있다.

 

 

 

 

 

결과 코드

import java.util.*;

public class Main
{
    public static void main(String[] args)
    {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m;
        String[] numlist;
        String result;

        for(int i = 0; i<n; i++)
        {
            result = "YES";
            m = scanner.nextInt();
            numlist = new String[m];
            for(int j = 0; j<m; j++)
            {
                numlist[j] = scanner.next();
            }
            Arrays.sort(numlist);
            for(int j = 0; j<m-1; j++)
            {
                if(numlist[j+1].startsWith(numlist[j]))
                {
                    result = "NO";
                    break;
                }
            }
            System.out.println(result);
        }
    }
}