[백준] 알고리즘 분류(트리,JAVA)5052번, 전화번호 목록

문제 링크

5052번: 전화번호 목록

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

이 문제에 핵심

 

1. 전화번호의 접두사가 다른 번호일 경우 일관성이 있지 않는 것이다.

2. 접두사가 다른 번호인 경우가 없을 때 일관성이 있는 것이다.

3. 입력받은 전화번호를 확인해서 일관성이 있으면 YES, 없으면 NO을 결과로 출력합니다.

 

알고리즘 진행 순서.

 

1. 입력된 전화번호 정보를 저장합니다.

 

2. 입력된 정보를 가지고 정렬해서 접두사에 다른 번호가 포함되는지 탐색합니다.

 

3. 각 테스트마다 일관성이 있으면 YES, 없으면 NO을 결과로 출력합니다.

 

처음에 트리를 이용해서 풀려고 진행해보았지만 감을 잡지 못하였습니다. 그래서 검색을 진행해보니 String.startWith으로 접두사를 확인할 수 있는 Methods가 존재한다는 것을 확인하고 사용하였습니다.

 

접두사 확인하기!

 

각 전화번호에 대하여 startWith을 모두 적용시켜보면 시간복잡도(N²)을 진행하게 됩니다.

 

하지만 오름차순 정렬을 한 뒤에 진행하면 접두사 관계가 있는 전화번호인 경우 바로 뒤에 있을 것입니다.

 

탐색을 진행할 때 바로 뒤에 있는 전화번호만 탐색하면 됩니다.

 

 

예제입력 1.

테스트케이스 1.

 

1. 입력된 전화번호 정보를 저장합니다.

 

n : 3

 

전화번호 : 9119762599991125426

 

2. 입력된 정보를 가지고 정렬해서 접두사에 다른 번호가 포함되는지 탐색합니다.

 

정렬 진행

911

91125426

97625999

 

91125426 : 911에 접두사를 포함하고 있습니다.

 

3. 입력받은 전화번호를 확인해서 일관성이 있으면 YES, 없으면 NO을 결과로 출력합니다.

 

일관성을 가지고 있지 않기 때문에

 

NO을 결과로 출력합니다.

 

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• 각 테스트케이스마다 전화번호들을 저장한 뒤 오름차순 정렬합니다.
• 정렬한 뒤 일관성 검사를 진행하는 search함수를 실행하였습니다.
• 일관성 검사의 결과를 BufferedWriter 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• search함수는 String.startWith을 이용하여 다른 전화번호가 접두사로 사용되었는지 확인합니다.
• search함수는 접두사로 사용되면 NO, 접두사를 사용되지 않으면 YES을 반환합니다.

 

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int t = Integer.parseInt(br.readLine());
        //각 테스트케이스 진행
        for(int i=0;i<t;i++) {
            int n = Integer.parseInt(br.readLine());
            String[] arr = new String[n];
            //전화번호 저장
            for (int j = 0; j < n; j++)
                arr[j] = br.readLine();

            Arrays.sort(arr);		//오름차순 정렬
            bw.write(search(arr) + "\n");	//일관성 결과 BufferedWriter 저장
        }
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //전화번호들 일관성 확인하는 함수
    static String search(String[] arr){
        for(int i=0;i<arr.length-1;i++){
            if(arr[i+1].startsWith(arr[i]))	//접두사로 사용될 경우
                return "NO";		//일관성 X, NO반환
        }
        return "YES";	//접두사 사용 X, 일관성 O, YES반환
    }
}