[Jungol] 정올 1885 접두사

출처: jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1158&sca=30b0

Approach

주어진 숫자 배열에서 임의의 어떤 숫자가 다른 숫자의 prefix(접두사)가 되는 경우가 있는지 판별

각 Test Case의 Input Data 개수 N (1 ~ 10,000)이고, 각 숫자의 길이는 100자리

→ long long 범위(19자리) 초과 → 문자열 처리

* Input Data가 정렬되지 주어지지 않음

 

- 입력 받은 문자열은 정렬되어 있지 않으므로 오름차순 정렬

- 접두사가 되는 문자열은 접두사를 포함하는 문자열의 바로 앞에 나온다.

  즉, A[i-1] 문자열이 A[i]의 접두사에 해당

  경우에 따라서는 A[i]뿐만 아니라 A[i+1], A[i+2], ...도 해당 될 수 있습니다.)

  But, A[i]가 A[i-1]을 접두사로 하지 않는데, A[i+1]이 A[i]를 접두사로 하는 경우는 생기지 않습니다.

 

▶ [해시] Hash란?

[해시] Hash란?

 

방법 1

- 오름차순 정렬된 문자열의 이웃한 문자열 검사

    문자열을 멤버로 가는 구조체 배열을 만들고 Merge Sort 이용

- 이웃한 문자열 중에서 접두문자열이 발생하는 곳이 한 곳이라도 생기면 "NO"

   한 곳도 생기지 않으면 "YES" 출력

---

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
 
const int LM = 10004;
int TC, N;
struct Data {
    char str[101];
}A[LM], trr[LM];
 
int strcmp(char *s, char *t) {
    while (*s && *s == *t)++s, ++t;
    return *s - *t;
}
 
int prefix(char *s, char *t) {
    // (최대 s 문자열 길이만큼) s와 t와 같은 값을 가지는 만큼 이동
    while (*s && *s == *t) ++s, ++t;
    // s == 0인 경우 t가 s를 접두사로 포함
    return !*s; // 문자 s가
}
void mergeSort(Data* arr, int start, int end) {
    // 1. base condition
    if (start + 1 >= end) return;
    // 2. divide
    int mid = (start + end) / 2, i = start, j = mid, k = start;
    mergeSort(arr, start, mid);
    mergeSort(arr, mid, end);
    // 3. merge
    while (i < mid && j < end) {
        if (strcmp(arr[i].str, arr[j].str) < 0) {
            trr[k++] = arr[i++];
        }
        else trr[k++] = arr[j++];
    }
    while (i < mid) trr[k++] = arr[i++];
    while (j < end) trr[k++] = arr[j++];
    // 4. copy
    for (i = start; i < end; ++i) arr[i] = trr[i];
}
 
bool process() {
    for (int i = 1; i < N; ++i) {
        if (prefix(A[i - 1].str, A[i].str))
            return true;
    }
    return false;
}
int main() {
    // freopen("input.txt", "r", stdin);
    int i;
    scanf("%d", &TC);
    while (TC--) {
        scanf("%d", &N);
        for (i = 0; i < N; ++i) {
            scanf("%s", A[i].str);
        }
 
        // 문자열 오름차순 정렬
        mergeSort(A, 0, N);
 
        // 접두사 여부 확인
        if (process())
            puts("NO");
        else
            puts("YES");
    }
} 

 

방법 2

- 입력된 문자열을 길이 별로 Hash Table에 보관 → Chaining 기법 이용(링크드 리스트)

- 짧은 길이 문자열부터 부분 문자열을 해싱하여 이미 저장된 접두사가 있는지 검사

  → 현재 문자열의 접두사가 발견되지 않는 경우 Hash Table에 추가

  → 접두사가 발견되는 경우가 존재한다면 "NO", 한번도 발생하지 않는다면 "YES "

* 각 Test Case마다 초기화에 유의

 

[시뮬레이션]

adjList[]에는 길이별로 문자열이 저장됩니다.

접두사 여부는 문자열 길이가 짧은 것부터 확인합니다.

위의 경우는 "911" → "91125426" → "97625999" 순입니다.

 

먼저 "911"의 부분 문자열인 "9", "91", "911"이 Hash Table에 존재하는지 확인합니다.

없으므로 "911" 문자열을 Hash Table에 넣습니다.

다음 문자열인 "91125426"의 부분 문자열 "9", "91", "911", "9112", "9112", ..., "91125426"이 Hash Table에 존재하는지 확인합니다.

"911"이 접두사로 존재하므로 결과적으로 "NO" 출력합니다.

 

※ (Code) Hash Table에서 접두사를 확인할 때, 부분 문자열 길이와 전체 문자열을 전달합니다.

"91125426"에서 부분문자열 길이 = 1 → "9"가 Hash Table에 존재?

"91125426"에서 부분문자열 길이 = 2 → "91"가 Hash Table에 존재?

"91125426"에서 부분문자열 길이 = 3 → "911"가 Hash Table에 존재?

---

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
 
typedef unsigned int UI;
const int LM = 10005;
const int SIZE = 1 << 14;
int N;
int strlen(char* s, int i = 0) {
    // default 매개변수 전달 값이 없는경우 i = 0 사용
    while (s[i]) ++i;
    return i;
}
 
// 문자열 t가 문자열 s를 접두사로 포함하는지 확인
int prefix(const char* s, const char* t) {
    while (*s && *s == *t) ++s, ++t;
    return *s == 0; // *s == '\0' 혹은 !*s
}
 
struct Node {
    char str[105];
    int len;
    Node* next;
    Node* alloc(Node* np) {
        next = np;
        return this;
    }
}buf[LM], *hTable[SIZE], *adjList[101];
 
void init() {
    int i;
    for (i = 0; i < 101; i++) adjList[i] = NULL;
    for (i = 0; i < SIZE; i++) hTable[i] = NULL;
}
 
void input() {
    int i, len;
    scanf("%d", &N);
    for (i = 0; i < N; i++) {
        scanf("%s", buf[i].str);
        len = buf[i].len = strlen(buf[i].str);
        // 문자열을 길이별로 구분하여 저장
        adjList[len] = buf[i].alloc(adjList[len]);
    }
}
 
bool probing(int hidx, int len, char* s) {
    Node* p = hTable[hidx];
    for (; p; p = p->next) {
        // 길이가 다른 경우 접두사를 확인할 필요가 업습니다.
        if (p->len == len && prefix(p->str, s))
            return true;
    }
    return false;
}
bool djb2(Node* now, char* s) {
    // now: 현재 객체, s: 현재 단어
    UI hidx = 5381;
    for (int i = 0; s[i]; i++) {
        hidx = ((hidx * 33) + s[i]) % SIZE;
        // 탐사 (접두사가 있는지 확인)
        if (probing(hidx, i + 1, s))
            return true;
    }
 
    //접두사를 못찾은 경우 : 해시테이블에 현재 단어를 추가
    hTable[hidx] = now->alloc(hTable[hidx]);
    return false;
}
 
bool process() {
    for (int i = 1; i < 101; i++) {
        Node* p = adjList[i]; // 문자열 길이가 작은것부터 확인
        for (; p; p = adjList[i]) { // 길이가 i인 문자열을 확인
            adjList[i] = p->next;
            if (djb2(p, p->str)) // 접두사를 포함하는지 확인
                return true; // 한 개라도 찾은 경우 종료
        }
    }
    return false;
}
 
int main() {
    // freopen("input.txt", "r", stdin);
    int tc;
    scanf("%d", &tc);
    while (tc--) {
        init();
        input();
        puts(process() ? "NO" : "YES");
    }
}