[14425] 문자열 집합

✔ 문자열 집합

[백준 14425]

문제 분석하기

집합 S에 속해 있는 단어들을 이용해 트라이 구조를 생성하고, 트라이 검색을 이용해 문자열 M개의 포함 여부를 카운트

손으로 풀어보기

1. 트라이 자료구조를 생성
   • 현재 문자열을 가리키는 위치의 노드가 공백 상태라면 신규 노드를 생성하고, 아니라면 이동
   • 문자열의 마지막에 도달하면 리프 노드라고 표시
2. 트라이 자료구조 검색으로 자료구조 S에 포함된 문자열을 셈
   • 부모-자식 관계 구조를 이용해 대상 문자열을 검색했을 때 문자열이 끝날 때까지 공백 상태가 없고,
     현재 문자의 마지막 노드가 트라이의 리프 노드라면 이 문자를 집합 S에 포함된 문자열로 셈

슈도코드 작성하기

N(집합 S의 문자열 개수) M(검사할 문자열 개수)
while(N만큼 반복하기) {
    text(집합 S의 문자열)
    현재 노드를 루트 노드로 설정하기
    for(i를 text 문자열 길이만큼 반복하기) {
        c(i번째 문자)
        if(c 변수에 해당하는 다음 노드가 null) 신규 노드 생성하기
            현재 노드를 c 변수 노드로 변경하기
        if(i가 문자열의 마지막이면) isEnd 변수를 true로 설정하기
    }
}
count(정답 변수)
while(M만큼 반복하기) {
    text(검색 문자열)
    현재 노드를 루트 노드로 설정하기
    for(i를 text 문자열 길이만큼 반복하기) {
        c(i번째 문자)
        if(c 변수에 해당하는 다음 노드가 null) 이 문자열 검색 종료
            현재 노드를 c 변수 노드로 변경하기
        if(i가 문자열의 마지막이고, 현재 노드의 isEnd값이 true이면) count값 올리기
    }
}
count 출력하기
class t노드 {
    next(다음 노드 배열)
    isEnd(마지막 문자열 여부 표시하기)
}

코드 구현하기

/**
 * 14425) 문자열_집합
 */
public class D069_14425 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // N(집합 S의 문자열 개수)
        int N = sc.nextInt();
        // M(검사할 문자열 개수)
        int M = sc.nextInt();
        tNode root = new tNode();
        while (N > 0) {
            // text(집합 S의 문자열)
            String text = sc.next();
            // 현재 노드를 루트 노드로 설정하기
            tNode now = root;
            // i를 text 문자열 길이만큼 반복하기
            for (int i = 0; i < text.length(); i++) {
                // c(i번째 문자)
                char c = text.charAt(i);
                // c 변수에 해당하는 다음 노드가 null
                if (now.next[c - 'a'] == null) {
                    // 신규 노드 생성하기
                    now.next[c - 'a'] = new tNode();
                }
                // 현재 노드를 c 변수 노드로 변경하기
                now = now.next[c - 'a'];
                // i가 문자열의 마지막이면
                if (i == text.length() - 1)
                    // isEnd 변수를 true로 설정하기
                    now.isEnd = true;
            }
            N--;
        }
        // count(정답 변수)
        int count = 0;
        while (M > 0) {
            // text(검색 문자열)
            String text = sc.next();
            // 현재 노드를 루트 노드로 설정하기
            tNode now = root;
            // i를 text 문자열 길이만큼 반복하기
            for (int i = 0; i < text.length(); i++) {
                // c(i번째 문자)
                char c = text.charAt(i);
                // (c 변수에 해당하는 다음 노드가 null
                if (now.next[c - 'a'] == null) {
                    // 이 문자열 검색 종료
                    break;
                }
                // 현재 노드를 c 변수 노드로 변경하기
                now = now.next[c - 'a'];
                // i가 문자열의 마지막이고, 현재 노드의 isEnd값이 true이면
                if (i == text.length() - 1 && now.isEnd)
                    // count값 올리기
                    count++;
            }
            M--;
        }
        // count 출력하기
        System.out.println(count);
    }
}

class tNode {
    // next(다음 노드 배열)
    // 알파벳 소문자로만 구성된 문자열을 저장하는 트라이의 각 노드는 각 노드가 26개짜리 포인터 배열을 가지고 있음
    // 알파벳 소문자 개수는 26개
    tNode[] next = new tNode[26];
    // isEnd(마지막 문자열 여부 표시하기)
    boolean isEnd;
}