[BaekJoon] 5052번 - 전화번호 목록 [Java][C++]

문제 링크

---

1. 문제 풀이

전화번호 목록의 일관성 여부를 판단하는 문제로 일관성이 없는 목록은 한 번호가 다른 번호의 접두어가 되는 경우다. 접두어를 통해 판단한다는 점에서 트라이 자료구조를 활용했는데 삽입 과정에서 다음 노드로 이동할 때 이미 삽입한 번호의 마지막 노드를 방문하면 새로 삽입하는 번호가 해당 번호의 접두어가 되므로 삽입에 실패하게 해줬다. 911을 삽입한 후 91125426을 삽입할 때 911의 마지막 1에서 해당 경우가 체크되므로 새로운 삽입하는 번호가 기존에 삽입한 번호의 접두어가 되는 경우를 체크할 수 있다. 다음은 새로 삽입하는 번호가 기존에 삽입한 번호의 접두어가 되는 경우를 찾아야하는데 이는 새로 삽입하는 번호가 트라이에서 한번도 새로운 노드를 만든 적이 없는지 판단하면 된다. 한번이라도 새로운 노드를 만들면 삽입 후 이후 cur 값이 unused 보다 1 작으므로 이를 통해 판단할 수 있다.

---

2. 코드

1. 풀이 [Java]

import java.io.*;

public class Main {

    static final int MX = 1 + 10000 * 10;
    static final int ROOT = 0;
    static int unused;
    static int[][] nxt;
    static boolean[] chk;

    static void init() {
        unused = ROOT + 1;
        nxt = new int[MX][10];
        chk = new boolean[MX];
    }

    static boolean insert(String s) {
        int cur = ROOT;
        for (char c : s.toCharArray()) {
            int idx = c - '0';
            if (nxt[cur][idx] == 0) nxt[cur][idx] = unused++;
            cur = nxt[cur][idx];
            if (chk[cur]) return false;
        }

        if (cur != unused - 1) return false;

        chk[cur] = true;
        return true;
    }

    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) {
            init();

            int n = Integer.parseInt(br.readLine());
            boolean flag = true;
            while (n-- > 0) {
                String s = br.readLine();
                if (!flag) continue;

                if (!insert(s)) flag = false;
            }

            if (flag) {
                bw.write("YES\n");
            } else {
                bw.write("NO\n");
            }
        }

        bw.flush();
    }
}

2. 풀이 [C++]

#include <bits/stdc++.h>
using namespace std;

const int MX = 1 + 10000 * 10;
const int ROOT = 0;
int unused;
int nxt[MX][10];
bool chk[MX];

void init() {
    unused = ROOT + 1;
    memset(nxt, 0, sizeof(nxt));
    memset(chk, 0, sizeof(chk));
}

bool insert(string& s) {
    int cur = ROOT;
    for (char c : s) {
        int idx = c - '0';
        if (nxt[cur][idx] == 0) nxt[cur][idx] = unused++;
        cur = nxt[cur][idx];
        if (chk[cur]) return false;
    }

    if (cur != unused - 1) return false;

    chk[cur] = true;
    return true;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int t;
    cin >> t;

    while (t--) {
        init();

        int n;
        cin >> n;
        bool flag = true;

        while (n--) {
            string s;
            cin >> s;
            if (!flag) continue;

            if (!insert(s)) flag = false;
        }

        if (flag) {
            cout << "YES\n";
        } else {
            cout << "NO\n";
        }
    }
}

---