[HackerRank] No Prefix Set

Problem

---

There is a given list of strings where each string contains only lowercase letters from a-j, inclusive. The set of strings is said to be a GOOD SET if no string is a prefix of another string. In this case, print GOOD SET. Otherwise, print BAD SET on the first line followed by the string being checked.

Note If two strings are identical, they are prefixes of each other.

 

Example

words = ['abcd', 'bcd', 'abcde', 'bcde']

Here 'abcd' is a prefix of 'abcde' and 'bcd' is a prefix of 'bcde'. Since 'abcde' is tested first, print

BAD SET  
abcde

words = ['ab', 'bc', 'cd'].

No string is a prefix of another so print

GOOD SET

 

Function Description
Complete the noPrefix function in the editor below.

noPrefix has the following parameter(s):
- string words[n]: an array of strings

 

Prints
- string(s): either GOOD SET or BAD SET on one line followed by the word on the next line. No return value is expected.

 

Input Format
First line contains n, the size of words[].
Then next n lines each contain a string, words[i].

 

Constraints
1 ≤ n ≤ 10^5
1 ≤  the length of words[i] ≤ 60
All letters in words[i] are in the range 'a' through 'j', inclusive.

 

Sample Input00

STDIN       Function
-----       --------
7            words[] size n = 7
aab          words = ['aab', 'defgab', 'abcde', 'aabcde', 'bbbbbbbbbb', 'jabjjjad']
defgab  
abcde
aabcde
cedaaa
bbbbbbbbbb
jabjjjad

 

Sample Output00

BAD SET
aabcde

 

Explanation
'aab' is prefix of 'aabcde' so it is a BAD SET and fails at string 'aabcde'.

 

Sample Input01

4
aab
aac
aacghgh
aabghgh

 

Sample Output01

BAD SET
aacghgh

 

Explanation
'aab' is a prefix of 'aabghgh', and aac' is prefix of 'aacghgh'. The set is a BAD SET. 'aacghgh' is tested before 'aabghgh', so and it fails at 'aacghgh'.

---

주어진 문자열 리스트가 있습니다. 각 문자열은 소문자 a부터 j까지의 문자로만 구성되어 있습니다. 문자열 집합은 다음과 같은 조건을 만족할 때 GOOD SET이라 합니다:

• 어떤 문자열도 다른 문자열의 접두어(prefix)가 아니어야 합니다.

위 조건을 만족하면 "GOOD SET"을 출력하고, 그렇지 않다면 "BAD SET"을 출력하며 위반된 첫 번째 문자열을 출력합니다.

참고: 두 문자열이 동일하면 서로의 접두어로 간주합니다.

 

예시 

• words = ['abcd', 'bcd', 'abcde', 'bcde']
  • 'abcd'는 'abcde'의 접두어이고, 'bcd'는 'bcde'의 접두어입니다. 'abcde'가 처음 위반된 경우이므로 "BAD SET\nabcde"를 출력합니다.
• words = ['ab', 'bc', 'cd'].
  • 어떤 문자열도 다른 문자열의 접두어가 아니므로 "GOOD SET"을 출력합니다.

함수 설명

noPrefix 함수는 다음 매개변수를 받습니다:

• List<String> words: 문자열의 배열

함수는 값을 반환하지 않으며, 조건에 따라 "GOOD SET" 또는 "BAD SET"을 출력합니다.

 

제약사항

• 1 ≤ n ≤ 10^5
• 1≤ words[i]의 길이 ≤ 60
• words[i]는 'a'부터 'j'까지의 문자로만 구성됩니다.

 

728x90

 

 

 

Solution

---

public static void noPrefix(List<String> words) {
    TrieNode root = new TrieNode();

    for (String word : words) {
        if (!insert(root, word)) {
            System.out.println("BAD SET");
            System.out.println(word);
            return;
        }
    }
    System.out.println("GOOD SET");
}

static class TrieNode {
    TrieNode[] children = new TrieNode[10];
    boolean isEndOfWord = false;

    TrieNode() {}
}

static boolean insert(TrieNode root, String word) {
    TrieNode current = root;
    for (int i = 0; i < word.length(); i++) {
        int index = word.charAt(i) - 'a';

        // 이미 접두어가 있거나, 접두어로서 확인되는 경우 BAD SET 반환
        if (current.children[index] == null) {
            current.children[index] = new TrieNode();
        } else if (i == word.length() - 1 || current.children[index].isEndOfWord) {
            return false;
        }
        
        current = current.children[index];
    }

    // 현재 단어가 이미 존재하는 다른 단어의 접두어인지 확인
    if (current.isEndOfWord) {
        return false;
    }

    // 단어 삽입 완료
    current.isEndOfWord = true;
    return true;
}

이 문제는 접두어를 빠르게 검색할 수 있는 트라이(Trie) 자료구조를 사용해 해결하는 것이 효율적입니다. 트라이를 사용하면 문자열이 입력될 때마다 다른 문자열의 접두어인지 여부를 확인할 수 있습니다.

 

 

1. TrieNode 클래스: 트라이의 노드를 정의합니다. children 배열은 'a'부터 'j'까지의 문자(총 10개)를 자식 노드로 가질 수 있도록 크기 10으로 정의합니다.
2. insert 함수: 새로운 단어를 트라이에 삽입하며, 접두어 조건을 위반하는지 확인합니다.
   • 문자열의 각 문자를 탐색하면서 트라이에 노드를 추가합니다.
   • 현재 노드가 이미 끝 노드이거나, 현재 단어가 다른 단어의 접두어라면 false를 반환하여 BAD SET 조건을 충족시킵니다.

 

---

1. TrieNode 클래스

• 먼저, TrieNode 클래스는 트라이의 한 노드를 정의하는 클래스입니다.
• TrieNode[] children = new TrieNode[10];
  • 설명: 자식 노드들을 저장하는 배열입니다. 각 노드는 최대 10개의 자식 노드를 가질 수 있습니다. 배열의 인덱스는 문자 'a'부터 'j'까지를 나타냅니다.
  • 사용 이유: 문자열의 각 문자에 대해 자식 노드를 가지게 되므로, children 배열을 사용하면 각 문자에 해당하는 자식 노드를 배열의 인덱스로 바로 접근할 수 있어 시간 효율성이 높아집니다.
  • 인덱스 할당 방법: 'a'가 0, 'b'가 1, ... 'j'가 9의 인덱스를 가집니다. 배열의 크기가 10인 이유는 문제에서 문자열이 소문자 'a'부터 'j'까지만 포함한다고 했기 때문입니다.
• boolean isEndOfWord = false;
  • 설명: 현재 노드가 어떤 단어의 마지막 문자인지 나타냅니다. 만약 isEndOfWord가 true라면 이 노드까지가 하나의 단어의 끝이라는 뜻입니다.
  • 사용 이유: 접두어 판별을 위해 사용됩니다. 예를 들어, "abc"라는 단어가 있고, "abcd"라는 단어를 삽입할 때 "abc" 노드의 isEndOfWord가 true라면 "abc"는 "abcd"의 접두어이므로 BAD SET 조건에 해당합니다.

1-1. TrieNode를 사용하는 이유

• 트라이는 문자열의 공통된 접두어를 공유할 수 있는 자료구조로, 문자열이 추가될 때마다 새로운 노드를 추가하면서 효율적으로 문자열을 저장하고 탐색할 수 있습니다.
• 트라이를 사용하면 문자열을 한 글자씩 따라가며 접두어를 빠르게 검사할 수 있습니다.
• insert 함수에서 문자열을 추가할 때, 이전에 추가된 문자열과의 접두어 관계를 빠르게 확인할 수 있습니다.
• 접두어 문제뿐 아니라, 문자열의 존재 여부 확인, 자동 완성 등에도 효과적입니다.

 

2. insert 메서드

 

1. int index = word.charAt(i) - 'a';
   • 설명: 현재 문자 word.charAt(i)를 가져와 a를 뺀 값으로 인덱스를 계산합니다. 예를 들어, 'a'는 index가 0이 되고, 'b'는 1, ..., 'j'는 9가 됩니다.
   • 이유: 'a'의 ASCII 값이 97이므로, word.charAt(i) - 'a'를 계산하면 'a'부터 'j'까지 0에서 9 사이의 인덱스가 됩니다. 이를 통해 문자 하나를 배열 인덱스에 매핑할 수 있습니다.
2. if (current.children[index] == null)
   • 설명: current 노드의 자식 노드 중 index 위치가 비어 있다면(null이라면), 아직 해당 문자를 포함하는 노드가 생성되지 않은 것입니다. 이 경우, 새로운 TrieNode를 생성해 children 배열의 index 위치에 연결합니다.
   • 이유: 트라이에 새로운 경로를 추가하기 위한 단계로, 단어가 트라이에 추가될 때마다 새로운 경로가 필요하면 노드를 생성합니다.
3. else if (i == word.length() - 1 || current.children[index].isEndOfWord)
   • 설명: 이 조건은 현재 단어가 다른 단어의 접두어인 경우 또는 반대로 어떤 단어가 현재 단어의 접두어인 경우에 false를 반환합니다.
   • 첫 번째 조건: i == word.length() - 1는 현재 단어가 트라이의 기존 경로와 동일한 경로로 구성되어 있을 때 false를 반환하여 BAD SET으로 판별합니다.
   • 두 번째 조건: current.children[index].isEndOfWord는 현재 문자가 이미 다른 단어의 끝 문자라면, 현재 단어가 그 단어의 접두어임을 나타내므로 false를 반환합니다.
4. current = current.children[index];
   • 설명: 다음 문자를 검사하기 위해 current를 해당 자식 노드로 이동시킵니다.
   • 이유: 현재 경로를 따라가며 트라이에 문자를 삽입하고, 접두어 관계를 검사하는 역할을 합니다.
5. if (current.isEndOfWord)
   • 설명: 루프가 끝난 후, 현재 노드(current)의 isEndOfWord가 true라면, 트라이에 동일한 단어가 이미 존재하거나 현재 단어가 다른 단어의 접두어라는 의미입니다. 이 경우 false를 반환해 BAD SET으로 판별합니다.
6. current.isEndOfWord = true;
   1. 설명: 트라이에 새로운 단어가 추가될 때 마지막 문자의 노드에 isEndOfWord를 true로 설정합니다.
   2. 이유: 현재 노드가 하나의 단어의 끝임을 표시하여, 이후 다른 단어가 이 경로와 접두어 관계가 있는지 확인할 수 있습니다.

 

3. isEndOfWord 플래그의 용도

• isEndOfWord = true: 현재 노드까지가 하나의 단어의 끝을 의미합니다.
• isEndOfWord = false: 현재 노드가 단어의 중간 지점이며, 다른 문자열의 일부일 수 있음을 의미합니다.