[BOJ] 5052 전화번호 목록 (Java)

문제 링크

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

 

 

문제 풀이

NullPointerException 해결

맞왜틀!!을 계속 외쳤다. Trie 알고리즘을 사용해서 고쳤는데, IntellJ에서 정상으로 실행된 코드가 백준에서 NullPointerException이 계속 나서 원인을 못찾았었다.

        for (int idx = 0; idx < testCase; idx++) {
            int telSize = Integer.parseInt(br.readLine().trim());
            Trie trie = new Trie();
            boolean isConsistent = true;  // 일관성 체크

            for (int telIdx = 0; telIdx < telSize; telIdx++) {
                String telNum = br.readLine().trim();

                // 새 번호를 삽입하기 전에 접두어 검사
                if (!trie.insert(telNum)) {
                    isConsistent = false;
                    break; // BREAK
                }
            }

처음에는 이렇게 접두사 검사 후 NO를 찾으면 break문을 통해 for문을 멈추고자 했다.

하지만, 계속되는 틀림에 왜 안되는가 고민했는데, 초기에 testCase의 String까지 모두 입력을 받는데,

중간에 break문으로 for문을 멈추면 telNum을 입력받지 못해서 에러가 난다.

Trie 알고리즘으로 insert를 하면서 추가적으로 필요없겠다 판단했던 부분이 NullPointerExcpetion이 일어나게 했다.

따라서 break 문을 빼면 해결된다.

코드

일반 정렬로 해결

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

/**
 * BOJ_5052_전화번호 목록
 * -> 자바에서 정렬 !! -> Arrays.sort(list)
 * -> str1.startsWith(str2)
 *  자바 문법들 좀 기억하기 ,,
 * */

public class Main {

    static BufferedReader br;
    static StringTokenizer st;
    static StringBuilder sb;

    // 전화번호 일관성 검사
    public static boolean isConsistent(String [] telList) {
        // 접두어 관계가 있다면, startsWith
        for (int telIdx = 0; telIdx < telList.length- 1; telIdx++){
            // 오름차순에 따라 다음 것을 이전것과 앞자리 비교
            if (telList[telIdx + 1].startsWith(telList[telIdx])) {
                return false;
            }
        }
        return true;
    }

    public static void run() throws IOException{

        int telCnt = Integer.parseInt(br.readLine().trim());
        String[] telList = new String[telCnt]; // 테스트 케이스에 넣을 번호 초기화
        for (int telIdx = 0; telIdx < telCnt; telIdx++){
            telList[telIdx] = br.readLine().trim(); // 전화번호 입력
        }
        Arrays.sort(telList); // 순자척으로 정렬

        if (isConsistent(telList)) sb.append("YES").append("\n");
        else sb.append("NO").append("\n");
    }

    public static void main(String[] args) throws IOException {

        br = new BufferedReader(new InputStreamReader(System.in));
        sb = new StringBuilder();

        int testCase = Integer.parseInt(br.readLine().trim());
        for (int tc = 1; tc <= testCase; tc++){
            run();
        }
        System.out.println(sb);
    }

}

 

Trie 알고리즘 응용

package BOJ;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;

public class BOJ_5052_전화번호목록 {

    static BufferedReader br;
    static StringBuilder sb;

    static class Node {
        Map<Character, Node> child = new HashMap<>();
        boolean isEnd;
    }

    static class Trie {
        Node root = new Node();

        // insert
        boolean insert(String str) {
            Node now = this.root;
            boolean isNew = false; 

            for (Character c : str.toCharArray()) {
                if (!now.child.containsKey(c)) {
                    now.child.put(c, new Node());
                    isNew = true;  // 새 노드가 추가됨
                }
                now = now.child.get(c);

                // 중간에 다른 번호가 이미 끝나는 지점이 있으면 접두어 관계 발생
                if (now.isEnd) {
                    return false;  // 접두어 관계가 있음
                }
            }

            // 새 번호가 기존 번호의 접두어인지 확인 (기존 번호들이 새 번호보다 짧은 경우)
            if (!isNew) {
                return false;  // 이미 다른 번호가 이 번호의 접두어임
            }

            now.isEnd = true;
            return true;  // 정상 삽입됨
        }
    }

    public static void main(String[] args) throws IOException {

        br = new BufferedReader(new InputStreamReader(System.in));
        sb = new StringBuilder();

        int testCase = Integer.parseInt(br.readLine().trim());

        for (int idx = 0; idx < testCase; idx++) {
            int telSize = Integer.parseInt(br.readLine().trim());
            Trie trie = new Trie();
            boolean isConsistent = true;  // 일관성 체크

            for (int telIdx = 0; telIdx < telSize; telIdx++) {
                String telNum = br.readLine().trim();

                // 새 번호를 삽입하기 전에 접두어 검사
                if (!trie.insert(telNum)) {
                    isConsistent = false;
                }
            }

            if (isConsistent) {
                sb.append("YES").append("\n");
            } else {
                sb.append("NO").append("\n");
            }
        }

        System.out.println(sb.toString());
    }
}