백준 19585 자바 - 전설 (boj 19585 java)

문제 : boj19585

 

 

  다른 의미로 전설이었다. 보통은 포기하고 넘어갔을텐데 이론상(?) 가능할 것 같아서 계속 하다보니 오기가 생겨서 끝까지 해보기로 했었다 ㅋㅋㅋ 풀고보니 자바한정으로 통과하기 어려운 문제였다. 시간초과난 로직으로 다른 언어론 통과가 되더라 ㅠ

 

시도한 내용들은 이하와 같다.

 

1. 이왜플(이게 왜 플래)을 외치며 모든쌍을 HashSet에 넣었다가 당연히 시간초과(이하 TLE).

-> 색상과 닉네임이 둘 다 최대 4000개씩 이므로 모든 쌍을 만들면 O(4000^2) 이라고 대충 생각해서 해봤었다. 하지만 String이란 점을 간과했다. String + String이 결국 두 문자열 길이의 합 만큼 시간복잡도가 들어가므로, 실제론 O(4000^2 * (1000+1000)) 이다. StringBuilder로 해도 O(4000^2 * 1000)이다.

StringBuilder의 append 타고 들어가면 저렇게 기존 배열에 뒤의 배열을 붙이는 부분이 있다. 따라서 닉네임의 길이만큼 시간복잡도가 들어간다.

2. 트라이로 시도해봄. 원랜 색상, 닉네임 둘 다 순방향으로 넣고 찾았는데, 당연히 TLE..

3. 중간중간 뭐 색상의 max길이, 닉네임의 max 길이 같은걸로 약간씩 깎아내려 했으나 전부 TLE -> 여기부터 다른 언어론 통과한 경우가 있었다.

4. Fast I/O도 넣어보고 한 byte씩 읽어서도 해봤으나 역시 TLE

5. 색상은 순방향, 닉네임은 역방향으로 트라이를 만들고(최근에 푼 '프로그래머스 - 가사 검색' 문제에서 힌트를 얻었다.), Q에 대해 우선 순방향으로 색상을 전부 찾아두고 Q에 대해 역방향으로 닉네임을 트라이에서 찾아보려 함. 근데 이것도 TLE -> 여기부턴 많은 언어들이 통과 가능했다.

 

6. 색상은 트라이로 구성하고, 닉네임은 해시셋으로 구성했다. 그래서 들어온 입력에 대해 우선 색상을 트라이로 찾고, substring한 그 뒷부분을 해시에서 찾는 방식으로 진행했다. 여기서 드디어 통과했다.

 

 

위의 내용으로 풀이가 될 것 같다. 정리하면 다음과 같다.

 

A. 이 문제의 경우 색상과 닉네임을 둘 다 해시셋으로 유지하는건 힘든게, Q로 들어온 문자의 중간 어디에서 잘라야할지 알 수 없다.

B. 따라서 Q로 들어온 문자의 앞부분을 빠르게 찾기 위해 앞부분에 해당하는 색상을 Trie로 구성해둔다.

C. 그리고 닉네임을 트라이로 구성하려면, 순방향으로 하게 되면 색상 입력이 'a, ab, abc, abcd, ...' 와 같은 경우 모든 경우에 대해 그 뒷부분의 닉네임을 찾아야 하므로 비효율적이다. 따라서 역방향으로 닉네임 Trie를 구성한다면, 색상 순방향 트라이를 진행하면서 매칭되는걸 전부 찾아둔 후, 역방향으로 닉네임 트라이를 순회하면서 길이 합이 현재 문자열과 동일한걸 찾으면 되므로 더 효율적이다.

-> 다만 이건 자바론 통과가 안된다.

-> 따라서 닉네임은 트라이가 아니라 해시셋으로 구성해뒀다.

-> 그럼 색상 트라이를 순회하며 문자를 찾으면 나머지 부분을 부분문자열로 변경하고(substring) 그걸 해시에서 찾는다.

 

 

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.StringTokenizer;

class Trie {
    boolean isWordEnd;
    Trie[] child;

    public Trie() {
        isWordEnd = false;
        child = new Trie[26];
    }

    public Trie addAndGetChild(char c) {
        if (child[c-'a'] == null)
            child[c-'a'] = new Trie();
        return child[c-'a'];
    }

    public Trie getChild(char c) {
        return child[c-'a'];
    }

    public void setWordEnd() {
        this.isWordEnd = true;
    }
}

public class Main {
    Trie cTrie = new Trie();    // 색상 트라이
    HashSet<String> nHs = new HashSet<>();
    int cMin, nMin, cMax, nMax;

    private boolean searchTeamName(String s) {
        int len = s.length();
        // 우선 팀명에 대해 앞 부분 부터 보면서 색상과 매칭되는걸 colorMatched에 기록
        Trie iter = cTrie;
        for (int i = 0; i < len; i++) {
            if (len-i < nMin)
                break;
            iter = iter.getChild(s.charAt(i));
            if (iter == null) break;
            if (iter.isWordEnd) {
                if (nHs.contains(s.substring(i+1)))
                    return true;
            }
        }
        return false;
    }

    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int c = Integer.parseInt(st.nextToken());
        int n = Integer.parseInt(st.nextToken());
        cMin = nMin = 1001;
        cMax = nMax = 0;
        for (int i = 0; i < c; i++) {
            String cur = br.readLine();
            int len = cur.length();
            if (len < cMin) cMin = len;
            if (len > cMax) cMax = len;
            // 이하 색상 트라이 삽입
            Trie iter = cTrie;
            for (int j = 0; j < len; j++) {
                iter = iter.addAndGetChild(cur.charAt(j));
            }
            iter.setWordEnd();
        }
        for (int i = 0; i < n; i++) {
            String cur = br.readLine();
            int len = cur.length();
            if (len < nMin) nMin = len;
            if (len > nMax) nMax = len;
            nHs.add(cur);
        }
        int q = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        while (q-->0) {
            String cur = br.readLine();
            boolean chk = cur.length() > cMax + nMax ? false : searchTeamName(cur);
            if (chk) {
                sb.append('Y').append('e').append('s').append('\n');
            } else {
                sb.append('N').append('o').append('\n');
            }
        }
        System.out.print(sb);
    }
    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}