5052번: 전화번호 목록

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

5052번: 전화번호 목록

각 문자열의 부분 문자열이 중복되는지를 찾는 문제이므로 trie를 사용할 수도 있고, 부분 문자열을 일일이 map에 저장해 풀 수도 있다.

- trie (포인터 기반)

트라이에 문자열을 저장하면서 기존에 입력받은 문자열을 발견할 경우, 긴급전화가 겹치므로 해당 테스트 케이스는 일관성이 없는 목록이라고 할 수 있다.

#include <iostream>

using namespace std;

// trie 클래스
class node {
public:
    // 현재 노드가 리프 노드라면 true
    bool is_leaf = false;
    // 뒤에 올 수 있는 문자 '0' ~ '9'
    node* next[10];

    // 모든 자식 노드를 NULL로 초기화
    node() { for (int i = 0; i < 10; i++) next[i] = NULL; }
    // c에 해당하는 자식을 반환
    node* push (char c) {
        int i = c - '0';
        // 해당 자식이 NULL이라면 생성
        if (next[i] == NULL) next[i] = new node();
        return next[i];
    }
};

// 각 테스트 케이스를 입력받아 실행
bool test_case() {
    // 주어진 경우가 가능하다면 true, 아니라면 false
    bool ans = true;
    // 문자열을 한 글자씩 입력받기 위한 버퍼
    char buf;
    // 테스트 케이스에서 주어지는 문자열의 개수
    int n;
    // trie: 트라이를 저장할 공간, ptr: trie를 탐색하기 위한 포인터
    node trie, *ptr;

    cin >> n;
    cin.get();

    // 테스트 케이스의 각 문자열에 대해
    while (n--) {
        ptr = &trie;

        // while문을 통해 문자열을 한 글자씩 탐색
        while ((buf = cin.get()) != '\n') {
            // 입력받은 문자를 trie에 push한 뒤
            ptr = ptr->push(buf);
            // 지금까지 입력받은 부분 문자열이 이전에 입력받은 전체 문자열일 때
            // 현재 테스트 케이스는 불가능한 경우이다
            if (ptr->is_leaf) ans = false;
        }
        
        // 현재 문자열이 이전에 입력받은 문자열의 부분 문자열이라면
        // ptr->next 중 NULL이 아닌 값이 존재하므로 이를 확인하면
        // 현재 테스트 케이스는 불가능한 경우이다
        for (int i = 0; i < 10; i++) if (ptr->next[i] != NULL) ans = false;
        // 문자열 입력을 마쳤으므로 현재 문자열의 끝을 표시
        ptr->is_leaf = true;
    }

    // 현재 테스트 케이스가 가능한 경우인지를 출력
    return ans;
}

int main() {
    int t;
    // 테스트 케이스의 수를 입력받은 뒤
    cin >> t;
    // 각 테스트 케이스가 일관성 있는 테스트 케이스인지 여부를 반환
    while (t--) printf("%s\n", test_case() ? "YES" : "NO");

    return 0;
}

 

- trie (인덱스 기반)

#include <iostream>

using namespace std;

#define MAX_N 10000
#define MAX_LEN 10
#define ALP 10

// 트라이의 각 노드
struct node {
    // child[i]: i에 해당하는 자식이 존재한다면 그 자식의 인덱스, 아니라면 0
    int child[ALP] = { 0, };
    // 현재 노드가 리프 노드라면 true, 아니라면 false
    bool is_leaf = false;
};

bool test_case() {
    // 주어진 테스트 케이스가 일관성이 있는 목록이라면 true, 아니라면 false
    bool ret = true;
    // 문자열을 한 글자씩 입력받을 공간
    char c;
    // n: 전화번호의 개수
    // i: 트라이에 접근하기 위한 인덱스, len: 트라이에 존재하는 노드 수
    int n, i, len = 0;
    // trie[i]: i번째로 push된 노드의 상태
    node trie[MAX_N * MAX_LEN];

    // 전화번호의 개수를 입력받은 뒤 개행 문자를 입력받아 에러 방지
    cin >> n;
    cin.get();

    // 각 전화번호에 대해
    while (n--) {
        // 루트 노드에서부터 차례로 push
        i = 0;
        // 전화번호의 각 글자에 대해
        while ((c = cin.get()) != '\n') {
            // 현재 테스트 케이스가 일관성이 없다면 continue
            if (!ret) continue;

            // 현재 글자에 해당하는 자식 노드가 없다면 자식 노드를 새로 생성
            if (!trie[i].child[c - '0']) trie[i].child[c - '0'] = ++len;
            // 현재 글자에 해당하는 자식 노드로 이동한 뒤
            i = trie[i].child[c - '0'];
            // 이전에 현재 전화번호의 부분 문자열이 입력된 적 있다면
            // 현재 테스트 케이스는 일관성이 없음
            ret &= !(trie[i].is_leaf);
        }
        // 전화번호 입력을 마쳤으므로 리프 노드를 설정
        trie[i].is_leaf = true;
        // 현재 노드에 자식 노드가 존재하면
        // 현재 전화번호를 부분 문자열로 삼는 전화번호가 존재하므로
        // 현재 테스트 케이스는 일관성이 없음
        for (int j = 0; j < ALP; j++) ret &= !(trie[i].child[j]);
    }

    // 입력받은 테스트 케이스가 일관성 있는 목록인지 여부를 반환
    return ret;
}

int main() {
    // 입출력 속도 향상
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int t;
    // 테스트 케이스의 수를 입력받은 뒤
    // 각 테스트 케이스가 일관성 있는 목록인지 여부를 출력
    for (cin >> t; t--; ) cout << (test_case() ? "YES" : "NO") << '\n';

    return 0;
}

 

- map

각 문자열을 배열과 map에 각각 저장한 뒤, 각 문자열의 부분 문자열이 map에 존재한다면 긴급전화가 겹치므로 해당 테스트 케이스는 일관성이 없는 목록이라고 할 수 있다.

#include <iostream>
#include <set>
#include <string>

using namespace std;

#define MAX_N 10000

// 각 테스트 케이스를 입력받아 실행
bool test_case() {
    bool ans = true;
    char buf;
    int n;
    set<string> s;
    string str[MAX_N];
    
    // 문자열의 수를 입력받은 뒤
    cin >> n;
    // 각 문자열을 배열과 map에 각각 저장
    for (int i = 0; i < n; i++) {
        cin >> str[i];
        s.insert(str[i]);
    }

    // 각 부분 문자열이 map에 존재하는지 확인
    for (int i = 0; i < n; i++) {
        // substr(i, j)의 시간 복잡도는 O(i + j)이므로
        // 빠른 연산을 위해 새 변수를 만들어 부분 문자열을 차례로 저장
        string lookup = "";
        for (int j = 0; j < str[i].size() - 1; j++) {
            lookup += str[i][j];
            ans &= s.find(lookup) == s.end();
        }
    }
    return ans;
}

int main() {
    int t;
    // 테스트 케이스의 수를 입력받은 뒤
    cin >> t;
    // 각 테스트 케이스가 일관성 있는 테스트 케이스인지 여부를 반환
    while (t--) printf("%s\n", test_case() ? "YES" : "NO");

    return 0;
}