[Gold I] AB - 27652

문제 링크

분류

자료 구조, 해싱, 트리, 트라이

문제 설명

집합 A,B와 문자열 S에 대하여, 다음 쿼리를 수행하는 프로그램을 작성하시오.

• add A S: A에 S를 추가한다.
• delete A S: A에서 S를 제거한다.
• add B S: B에 S를 추가한다.
• delete B S: B에서 S를 제거한다.
• find S: A의 원소의 접두사와 B의 원소의 접미사를 이어 붙여 S가 되는 경우의 수를 출력한다. 원소가 다르거나 접두사(접미사)가 다르면 다른 경우로 센다. 빈 접두사(접미사)는 고려하지 않는다.

초기에 A,B 는 비어있으며, 이미 존재하는 원소를 추가하거나 존재하지 않는 원소를 제거하는 쿼리는 주어지지 않는다.

입력

첫째 줄에 쿼리의 개수 Q가 주어진다. (1≤Q≤1000)

둘째 줄부터 Q개의 줄에 걸쳐 쿼리가 한 줄에 하나씩 주어진다. 쿼리에 등장하는 문자열은 영어 소문자로 이루어지며, 길이는 1 이상 1000 이하이다.

find 쿼리는 적어도 한 번 주어진다.

출력

find 쿼리의 답을 한 줄에 하나씩 출력한다.

풀이

시간 제한이 2초이고, 문자열의 최대 길이가 1000이기에, Hashtable을 이용해서 풀 수 있었다. 다른분의 풀이를 보니까 Trie 자료구조를 써서 풀이하셨던데, Trie를 쓴 풀이도 생각해봐야겠다.

import java.io.*;
import java.util.*;

class Main {

    public static final BufferedReader BR = new BufferedReader(new InputStreamReader(System.in));
    int Q;
    Hashtable<String, Long> A;
    Hashtable<String, Long> B;
    String[] commands;

    public static void main(String[] args) throws Exception {
        Main main = new Main();
        main.init();
        main.solution();
    }

    void init() throws Exception {
        Q = Integer.parseInt(BR.readLine());
        A = new Hashtable<>();
        B = new Hashtable<>();
        commands = new String[Q];
        int i = 0;
        while (i < Q) {
            commands[i] = BR.readLine();
            i += 1;
        }
    }

    void find(String toFind) {
        long answer = 0;
        StringBuilder findA = new StringBuilder();
        StringBuilder findB = new StringBuilder(toFind);
        for (int i = 0; i < toFind.length(); i++) {
            findA.append(toFind.charAt(i));
            findB.deleteCharAt(0);
            String strA = findA.toString();
            String strB = findB.toString();
            if (A.containsKey(strA) && B.containsKey(strB)) {
                answer += A.get(strA) * B.get(strB);
            }
        }
        System.out.println(answer);
    }
    void add(String AB, String toAdd) {
        if (AB.equals("A")) {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < toAdd.length(); i++) {
                sb.append(toAdd.charAt(i));
                String str = sb.toString();
                A.put(str, (A.containsKey(str) ? A.get(str) + 1 : 1));
            }
        } else {
            StringBuilder sb = new StringBuilder(toAdd);
            for (int i = 0; i < toAdd.length(); i++) {
                String str = sb.toString();
                B.put(str, (B.containsKey(str) ? B.get(str) + 1 : 1));
                sb.deleteCharAt(0);
            }
        }
    }

    void delete(String AB, String toDelete) {
        if (AB.equals("A")) {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < toDelete.length(); i++) {
                sb.append(toDelete.charAt(i));
                String str = sb.toString();
                A.put(str, (A.containsKey(str) ? A.get(str) - 1 : 0));
            }
        } else {
            StringBuilder sb = new StringBuilder(toDelete);
            for (int i = 0; i < toDelete.length(); i++) {
                String str = sb.toString();
                B.put(str, (B.containsKey(str) ? B.get(str) - 1 : 0));
                sb.deleteCharAt(0);
            }
        }
    }
    
    void solution() {
        for (String command : commands) {
            String[] query = command.split(" ");
            if (query[0].equals("find")) {
                find(query[1]);
            } else if (query[0].equals("add")) {
                add(query[1], query[2]);
            } else {
                delete(query[1], query[2]);
            }
        }
        
    }


}