프로그래머스 - 전화번호 목록

https://programmers.co.kr/learn/courses/30/lessons/42577

 

문제 내용

전화번호들이 적힌 전화번호부가 있다.
한 번호가 다른 번호의 접두사인 경우가 없는지 확인하자.

“119”, “97674223”, “1195524421”이 있으면,
“119“는 “1195524421” 의 접두사이다.

접두사가 있다면 false, 없으면 true를 리턴하자.

 

제한 사항

• 1 <= 전화번호 수 <= 1,000,000
• 1 <= 전화번호 길이 <= 20

 

1. 정렬하기 - O(NlogN)

 

전화번호부에 다음 번호들이 있다고 생각해보자.

["345", "123", "987412", "12453", "123987"]

전화번호들이 제대로 된 형태로 정렬되어 있지 않다.
만약 전화번호들을 정렬 함수를 통해 정렬하면 어떻게 될까?

["123", "123987", "12453", "345", "987412"]

위와 같이 사전순으로 정렬이 된다.

사전순으로 정렬을 하면 어떤 효과가 있을까?
비슷한 단어로 시작하는 단어들이 서로 가까이 있게 된다.

"다리"와 "다리미"는 가까워지고,
"다리"와 "햄버거"는 멀어진다.

"123"과 "123987"은 가까워지고
"123"과 "987412"는 멀어진다.

 

그러면 다음과 같은 전략을 세울 수 있다.

 

---

정렬을 한 전화번호부를 살펴보면서, i번째 전화번호가 i+1번째 전화번호의 접두사라면, false를 리턴한다.
모든 전화번호를 찾았는데 그런 번호가 없다면, true를 리턴한다.

---

 

굳이 i번째 전화번호에서 i+1, i+2…를 계속 찾아볼 필요는 없다. i+1번째 전화번호가 i를 접두사로 쓰지 않으면, 그 뒤의 번호는 볼 필요도 없이 접두사로 쓰지 않는 단어들 뿐이다.

만약 "123" 뒤에 "12453"이 나왔다면,
이 뒤로는 "123"으로 시작하는 전화번호가 나올 수 없다.
사전순으로 정렬했는데도 "12453" 다음에 "123987"이 나왔다면, 그것은 정렬을 잘못한거다.
"다리" 다음에 "다시마"가 나왔는데, 그 뒤에 "다리미"가 나온다면 그 사전이 잘못된거다.

그러면 다음 동작을 통해 답을 얻어보자.

 

---

1. 0에서부터 n-2까지의 전화번호를 탐색하자.
2. i번째 문자를, i+1번째 문자의 0번째부터 i번째 문자의 길이만큼 잘라낸 부분 문자열(substring)과 비교를 하면서 탐색해나가자.
   1. 만약 i가 i+1의 부분 문자열이라면 false를 리턴하자.
3. 끝까지 순회했는데도 접두어를 찾지 못했으면 true를 리턴하자.

---

 

위의 과정에서, i번째 문자가 i+1번째 문자보다 긴 경우가 나올 수도 있다.
C++과 Python의 부분 문자열을 구하는 함수는 부분 문자열 시작 지점과 부분 문자열의 길이를 인자로 받아들인다. 만약 이 과정에서 문자열의 길이를 넘어서게 된다면, 자동으로 끊어준다.

예) “12345”에서 substr(3,111)을 한다면, “45”까지만 돌려준다.

하지만 Java의 경우, 부분 문자열 시작 지점과 부분 문자열 끝 지점을 인자로 받아들이므로, i 번호가 i+1보다 긴지 확인하자.

그럼 코드를 작성해보자.

 

solution_sort.cpp

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

bool solution(vector<string> phone_book) {
    sort(phone_book.begin(), phone_book.end());
    
    for (int i=0;i<phone_book.size()-1; ++i)
    {
        if (phone_book[i] == phone_book[i+1].substr(0, phone_book[i].size()))
            return false;
    }
    return true;
}

 

2. 해시맵 사용하기 - O(kN) - k는 문자열 길이

 

정렬로도 풀 수 있지만, 이 문제의 카테고리는 해시다. 해시로도 풀어보자.

그렇다면 해시로는 어떻게 풀어야 할까?
해시로는 어떻게 접두사의 존재 여부를 찾아야 할까?

["123", "123987", "12453", "345", "987412"]

이 예제를 다시 한번 살펴보자.

"123"이 가질 수 있는 접두사는 "1"과 "12"다.
그러면 전화번호부 목록에서 "1"과 "12"중 하나라도 있으면, "123"은 무언가를 접두사로 쓰고 있다는 이야기다.

"123987"이 가질 수 있는 접두사는 "1", "12", "123", "1239", "12398"이다.
그러면 전화번호부 목록에서 "1", "12", "123", "1239", "12398"중 하나라도 있으면, "123987"은 무언가를 접두사로 쓰고 있다는 이야기다.

그렇다면 전화번호부 목록에서 "1", "12"등, 특정 문자열의 존재 여부를 어떻게 찾을까?
바로 여기서 해시를 사용하는 것이다.

그러면 해시를 사용하여 접두어를 찾기 위한 다음과 같은 과정을 생각해보자.

 

---

1. 전화번호부의 모든 문자열들을 해시 자료구조에 집어넣는다.
2. 전화번호부의 모든 번호를 순회한다.
   1. 현재 순회중인 전화번호에서 를 하나씩 더해가며, 이 문자열이 해시 자료구조에 존재하는지 확인한다.
      ex) “12453”일 경우, “1”, “12”, “124”, “1245”에 대해 찾아본다.
   2. 있으면 false를 리턴한다.
3. 모든 번호를 탐색했다면, true를 리턴한다.

---

 

그러면 코드를 작성해보자.

 

solution_hash.cpp

#include <string>
#include <vector>
#include <unordered_set>

using namespace std;

bool solution(vector<string> phone_book) {
	unordered_set<string> st;

	for (string& str : phone_book)	st.insert(str);
	for (string& str : phone_book)
	{
		string substr = "";
		for (int i = 0; i < str.length()-1; ++i)
		{
			substr += str[i];
			if (st.find(substr) != st.end())
				return false;
		}
		st.insert(str);
	}

	return true;
}

 

3. trie 사용하기 - O(kN) - k는 문자열 길이

 

놀랍게도 이 문제를 푸는 또 다른 방법이 있다.
문자열을 다루는 데 사용하는 자료구조, 트라이(trie) 를 이용하여 풀 수도 있다!

그런데 트라이라는게 뭔지 모르니, 위키를 찾아보자.

https://en.wikipedia.org/wiki/Trie

요약하자면, 트라이는 트리의 일종이며, 순서를 가지는 자료구조를 저장할 때 사용할 수 있다. 그리고 문자열은 순서를 가지는 자료구조이다. 따라서 trie에 저장할 수 있다.

그러면 전화번호부를 트라이 자료구조로 만들어보자.

["123", "12345"]

전화번호 문자열에서 나올 수 있는 문자의 종류는 총 10가지다. (0~9)
그러면 하나의 node가 가질 수 있는 child의 개수는 10개다.

다음 그림부터는 간단하게 동그라미로 표현한다.
동그라미여도 저런 식으로 생겼다고 생각하자.

처음 node에서 시작해서, 주어진 문자열을 순회하면서 node간의 이동을 수행한다.

0을 만났을 때는 0을 가리키는 node로 이동한다.
1을 만났을 때는 1을 가리키는 node로 이동한다.
…
9를 만났을 때는 9를 가리키는 node로 이동한다.

처음에는 시작 node 하나만 있을 것이다.
만약 1을 만나서 1을 가리키는 node로 이동해야 하는데, 해당 node가 없다면, 그 때 새로 1을 가리키는 쪽에 node를 만들어주면 된다.

그리고 진행하다 보면, 언젠가는 마지막 문자를 만나 끝이 나는 경우가 있다. 이럴 경우, 마지막으로 이동한 node에 다음과 같은 표시를 해야 한다.

“여기에서 끝났다! 여기까지가 하나의 문자열!”

그러면 다음과 같은 형태의 트라이가 만들어지게 된다.

만약 위와 과정 중에서 node의 끝을 표시하지 않으면 어떻게 될까?

"123"을 트라이 자료구조에 넣은 뒤, "12345"를 넣는다고 생각해보자. "123"과 "12345"는 둘 다 "123"으로 시작한다.
따라서 "12345"를 트라이 자료구조에 넣을 때, 처음 "123"은 새로운 node를 생성하지 않아도 괜찮다.

하지만 그 이후로는 어떨까? "123" 뒤에는 새로운 node가 없기 때문에 새롭게 '4'와 '5'에 대한 node를 생성해야 한다.
그러면 이 때의 트라이 형태는 다음과 같다.

이제 이 트라이 자료구조를 통해서 "12345"를 포함하는 문자열이 있다는 사실은 알 수 있다. 그리고 이 다음으로 갈 수 있는 노드가 어디에도 없으므로, "12345"가 끝임을 알 수 있다.
하지만 "123"도 분명히 자료구조에 넣었던 문자열이다. 이제 "123"의 존재는 어떻게 알아차려야 할까?

"123"을 계속 따라갈 수 있다고 해서 "123"을 집어넣었다는 것이 확실한 것은 아니다. 우리는 "12"나 "1234"를 넣지는 않았지만, 해당 문자열을 집어넣으면 새로 생성하는 node 없이 끝까지 따라갈 수 있지 않은가?

그래서 "123"을 끝까지 따라갔을 때, 여기에서 끝난 문자열이 있다는 것을 알려주는 플래그가 필요하다.
"123"과 "12345" 트라이 자료구조를 플래그를 추가해서 만들면 다음과 같이 된다.

그렇다면, "123"과 "12345"에 대한 트라이를 만들면서, "123"이 "12345"의 접두사라는 사실은 어떻게 확인하면 될까?

"123"은 맨 처음으로 들어오는 문자열이다. 새롭게 구축하면 된다.

"12345"를 만들다 보면, '3' 지점에서 여기서 끝났다는 기록을 확인할 수 있다. 그렇다는 것은, "12345"의 부분문자열인 "123"이 존재한다는 것이다.
따라서, 이 뒤로는 볼 것도 없이 false를 리턴하면 된다. 여기서 더 찾아봤자, 특정 문자의 접두사가 존재한다는 사실은 변하지 않기 때문이다.

반대로 "12345"가 먼저 오고, "123"이 오면 어떻게 될 까?

"12345"는 맨 처음으로 들어오는 문자열이다. 새롭게 구축하면 된다.

"123"을 만들다보면, 이미 모두 있는 노드여서 새롭게 노드를 만들 필요가 없다. 마지막까지 새로운 노드를 만들지 않았다는 것은, 어떤 문자열이 이 문자열을 접두사로 쓰고 있다는 것을 의미한다. 따라서, 이 뒤로는 볼 것도 없이 false를 리턴하면 된다.

그러면 "123", "124"가 들어오면 어떻게 될 까?

"123"은 맨 처음으로 들어오는 문자열이다. 새롭게 구축하면 된다.

"124"의 경우, "12"까지는 기존의 노드를 따라오게 되나, '4'에서 새롭게 노드를 생성하게 된다.

따라서 진행하는 동안 마지막 노드라는 표시도 만나지 못했고, 모든 문자열은 각자 새로 생성한 노드가 있다.
따라서, 전화번호부에는 어떠한 문자열도 특정 문자열의 접두사가 되지 않는다는 것을 의미한다.
그러므로 true를 리턴하면 된다.

그러면 이를 코드로 표현해보자.

 

#include <string>
#include <vector>

using namespace std;

struct node
{
    node* nd[10];
    bool isEnd;
    node() : isEnd(false), nd() {}
};

bool solution(vector<string> phone_book) {
    node head;
    
    for (string str : phone_book)
    {
        node* current = &head;
        bool isSub = true;
        
        for (char c : str)
        {
            int idx = c - '0';
            if (nullptr == current->nd[idx])
            {
                isSub = false;
                current->nd[idx] = new node();                
            }
            
            current = current->nd[idx];
            if (current->isEnd) return false;
        }
        
        if (isSub)
		return false;
        current->isEnd = true;
    }
    
    return true;
}

 

트라이 자료구조는 알아두면 유용하게 사용할 수 있는 자료구조다. 여러 문자열이 주어지고, 이를 기반으로 특정 문자열을 검색하는 동작이 많을 경우에 유용하다. 알고리즘 문제들 중에는 이를 활용한 문제들이 종종 보이니, 기억해 뒀다가 느낌이 온다면 적절하게 활용해보자.