[백준] 5052번: 전화번호 목록 Java

 

문제

전화번호 목록이 주어진다. 이때, 이 목록이 일관성이 있는지 없는지를 구하는 프로그램을 작성하시오.

전화번호 목록이 일관성을 유지하려면, 한 번호가 다른 번호의 접두어인 경우가 없어야 한다.

예를 들어, 전화번호 목록이 아래와 같은 경우를 생각해보자

• 긴급전화: 911
• 상근: 97 625 999
• 선영: 91 12 54 26

이 경우에 선영이에게 전화를 걸 수 있는 방법이 없다. 전화기를 들고 선영이 번호의 처음 세 자리를 누르는 순간 바로 긴급전화가 걸리기 때문이다. 따라서, 이 목록은 일관성이 없는 목록이다. 

 

입력

첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1 ≤ n ≤ 10000) 다음 n개의 줄에는 목록에 포함되어 있는 전화번호가 하나씩 주어진다. 전화번호의 길이는 길어야 10자리이며, 목록에 있는 두 전화번호가 같은 경우는 없다.

 

출력

각 테스트 케이스에 대해서, 일관성 있는 목록인 경우에는 YES, 아닌 경우에는 NO를 출력한다.

 

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

5052번: 전화번호 목록

접근

트라이를 이용한 문제입니다.

번호를 부모와 자식 관계로 입력시키고, 번호 입력이 끝나는 경우 체크합니다.

만약 번호 입력 도중 번호 종료 표시를 만나는 경우,

다른 전화번호로 연결이 됨으로 NO를 출력합니다.

모든 전화번호 입력이 완료되면 YES를 출력합니다.

 

구현

먼저 핸드폰 번호를 정의할 PhoneNumber 클래스를 정의합니다.

이 클래스에는 숫자와 전화번호가 끝남을 체크하는 end, 다음 숫자를 입력할 수 있는 PhoneNumber 배열이 있습니다.

//전화번호 숫자 클래스
static class PhoneNumber{
    //해당 숫자
    int n;
    //끝났음을 체크
    boolean end=false;
    //자식들, 0-9 숫자
    PhoneNumber[] children=new PhoneNumber[10];
    //기본생성자
    public PhoneNumber() {};

    public PhoneNumber(int n) {
        this.n=n;
    }
}

 

다음으로 트라이를 정의합니다.

입력만을 문제를 함으로 set만 정의해주었습니다.

1) 전화번호 탐색 시, end가 true라면 false를 리턴합니다.

(123, 12345 인 경우)

2) 모든 탐색이 종료되었다면, 현재 위치한 PhoneNumber 객체에 자식들이 존재한다면 false를 리턴합니다.

(12345, 123 인 경우) 

3) 모든 검사를 통과하면 정상적으로 입력이 된 경우임으로 true를 리턴합니다.

static class Trie{
    //root 생성
    PhoneNumber root = new PhoneNumber();
    //char 형을 int 형으로 변환
    public int charToInt(char c) {
        return c-'0';
    }
    //트라이에 전화번호 넣기
    public boolean setPhoneNumber(String phoneNumber) {
        PhoneNumber parent = root;
        int no;
        for(char c:phoneNumber.toCharArray()) {
            //숫자 변환
            no=charToInt(c);
            //null이면 새로 생성
            if(parent.children[no]==null) {
                parent.children[no]=new PhoneNumber(c);
            }
            //부모 재설정
            parent = parent.children[no];
            //이미 끝난 전적이 있다면 false 리턴
            if(parent.end) {
                return false;
            }
        }
        //단어가 끝났음을 체크
        parent.end=true;
        //자식들 있는지 검사, 있다면 false
        for(PhoneNumber pn:parent.children) {
            if(pn!=null) return false;
        }
        //모든 검사 통과했음으로 true
        return true;
    }
}

 

이제 메인에서 데이터를 입력받아 YES와 NO를 출력합니다.

public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    int t=Integer.parseInt(br.readLine());
    while(t-->0) {
        //전화번호 수
        int n=Integer.parseInt(br.readLine());
        //트라이 생성
        Trie trie = new Trie();
        //일관성 체크
        boolean isConsistency = true;
        //탐색
        for(int i=0;i<n;i++) {
            String phoneNumber = br.readLine();
            //일관성이 true이고, 핸드폰 번호를 트라이에 넣을 수 없다면
            if(isConsistency&&!trie.setPhoneNumber(phoneNumber)) {
                //일관성 false;
                isConsistency=false;
            };
        }
        //일관성이 있으면 YES, 아니면 NO 출력
        bw.append(isConsistency?"YES":"NO").append("\n");
    }
    bw.close();
    br.close();
}

 

 

전체 코드는 다음과 같습니다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {
	//https://www.acmicpc.net/problem/5052
	
	static class Trie{
		//root 생성
		PhoneNumber root = new PhoneNumber();
		//char 형을 int 형으로 변환
		public int charToInt(char c) {
			return c-'0';
		}
		//트라이에 전화번호 넣기
		public boolean setPhoneNumber(String phoneNumber) {
			PhoneNumber parent = root;
			int no;
			for(char c:phoneNumber.toCharArray()) {
				//숫자 변환
				no=charToInt(c);
				//null이면 새로 생성
				if(parent.children[no]==null) {
					parent.children[no]=new PhoneNumber(c);
				}
				//부모 재설정
				parent = parent.children[no];
				//이미 끝난 전적이 있다면 false 리턴
				if(parent.end) {
					return false;
				}
			}
			//단어가 끝났음을 체크
			parent.end=true;
			//자식들 있는지 검사, 있다면 false
			for(PhoneNumber pn:parent.children) {
				if(pn!=null) return false;
			}
			//모든 검사 통과했음으로 true
			return true;
		}
	}
	
	//전화번호 숫자 클래스
	static class PhoneNumber{
		//해당 숫자
		int n;
		//끝났음을 체크
		boolean end=false;
		//자식들, 0-9 숫자
		PhoneNumber[] children=new PhoneNumber[10];
		//기본생성자
		public PhoneNumber() {};
		
		public PhoneNumber(int n) {
			this.n=n;
		}
	}
	
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int t=Integer.parseInt(br.readLine());
		while(t-->0) {
			//전화번호 수
			int n=Integer.parseInt(br.readLine());
			//트라이 생성
			Trie trie = new Trie();
			//일관성 체크
			boolean isConsistency = true;
			//탐색
			for(int i=0;i<n;i++) {
				String phoneNumber = br.readLine();
				//일관성이 true이고, 핸드폰 번호를 트라이에 넣을 수 없다면
				if(isConsistency&&!trie.setPhoneNumber(phoneNumber)) {
					//일관성 false;
					isConsistency=false;
				};
			}
			//일관성이 있으면 YES, 아니면 NO 출력
			bw.append(isConsistency?"YES":"NO").append("\n");
		}
		bw.close();
		br.close();
	}
}