[전화번호 목록] - 해쉬 ★★★☆ / 복습 ○

[ 문제 ] : https://programmers.co.kr/learn/courses/30/lessons/42577

코딩테스트 연습 - 전화번호 목록

---

[ 문제 접근 ]

 

결국 못풀고 틀렸던 문제.

 

처음에는 phone_book을 unordered_set에 넣고, unordered_set에서 전화번호 길이 순서로 하나씩 꺼내서 나머지랑 비교하는 방법으로 푸려고 했으나, unordered_set 은 원소의 순서를 보장해주지 않으니, phone_book을 길이 순으로 정렬하고 앞에서부터 unordered_set 이랑 비교 하는 방법으로 접근.

---

[ 첫번째 풀이 ]

 

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

using namespace std;

/*  # 1번째 풀이( 정확성 테스트 통과 / 효율성 테스트 실패)
- 문제 : [전화번호 목록] https://programmers.co.kr/learn/courses/30/lessons/42577
- 접근 방식 :
	처음에는 phone_book을 unordered_set에 넣고,
    unordered_set에서 전화번호 길이 순서로 하나씩 꺼내서 나머지랑 비교하는 방법으로 푸려고 했으나,
    unordered_set 은 원소의 순서를 보장해주지 않으니,
    phone_book vector를 문자열 길이 순서로 정렬하고 앞에서부터 unordered_set 이랑 비교 하는 방법으로 접근.
- 시간 복잡도 : O(n^2) ?
*/

bool cmp(const string& a,const string& b) {
	return a.length() < b.length();
}
bool solution(vector<string> phone_book) {
	//bool answer = true;
	unordered_set<string> hash_set;

	sort(phone_book.begin(), phone_book.end(), cmp);

	for (auto& elem : phone_book)  hash_set.insert(elem);

	
	for (int i = 0; i < phone_book.size(); i++) {
		int size = phone_book[i].length();
        
		hash_set.erase(hash_set.find(phone_book[i]));  // 비교할 문자를 hash_set에서 삭제.
		
        // hash_set에 있는 나머지 문자들과 비교.
		for (unordered_set<string>::iterator itr = hash_set.begin(); itr != hash_set.end();itr++) {
			if(size > (*itr).length()) continue;  // 시간 복잡도 줄이고자.

			if (phone_book[i] == (*itr).substr(0, size)) return false;
						
		}
	}

	return true;
}

 

[ 다른 사람 풀이 ]

#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(); ++i)
    {
        for(int j = i + 1; j < phone_book.size(); ++j)
        {
            if(phone_book[i] == phone_book[j].substr(0, phone_book[i].size()))
                return false;
        }
    }
    
    return true;
}

 

위는 다른 사람 블로그의 코드인데 이게 어떻게 통과되는지 모르겠다.

시간 복잡도도 자명하게 O(n^2) 아닌가 싶은데..

 

억울해서 실행해보니 그럼 그렇지!! 통과하지 못한다.

 

 

2021년 3월 4일에 테스트 케이스가 변경되었다는데 그전에 풀었던 사람인것 같다. 

 

근데 아래 처럼 이중 for문을 없애주면 통과가 된다.

 

[ 다른 사람 풀이 ]

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

bool solution(vector<string> phone_book) {
    bool answer = true;
    sort(phone_book.begin(), phone_book.end());
    
    for(int i=0; i<phone_book.size()-1; i++) {
        //정렬을 먼저 했으므로 phone_book[i] < phone_book[i+1] 항상 크기 때문에 이중 포문 불필요
        //string substr (size_t pos = 0, size_t len = npos)
        if (phone_book[i] == phone_book[i+1].substr(0, phone_book[i].size()))
            return false;
    }
    
    return answer;
}

 

그대로 난 hash 로 풀고 싶어서 다른 방법을 찾아봤다.

 

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

using namespace std;

bool solution(vector<string> phone_book) {
    sort(phone_book.begin(), phone_book.end()); // 정렬
    
    unordered_set<string> hash_map;
    hash_map.insert(phone_book[0]); // 첫번째 문자열은 접두어 해시맵에 있는지 확인할게 없으니 저장만
    for(int i = 1; i < phone_book.size(); ++i){ // 두번째 문자열부터 아래 과정!
        // 1. 접두어가 있는지 확인
        string str = "";
        for(int j = 0; j < phone_book[i].length(); ++j){
            str += phone_book[i][j]; // "abc" 라면 차례대로 "a", "ab", "abc"
            if (hash_map.find(str) != hash_map.end()) // 해시맵에 존재한다면 false 리턴 후 종료
                return false;
        }
        // 2. 내가 다른 단어의 접두어가 될 수도 있으니 나를 해시맵에 저장
        hash_map.insert(phone_book[i]);  
    }

    return true; // 한번도 리턴되지 못했다면 접두어 번호가 없는 것이다.
}

위와 같은 방법이 있었는데 랜덤한 

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

using namespace std;


bool cmp(const string& a,const string& b) {  // 문자 길이가 긴거부터 내림차순.
	return a.length() > b.length();
}

bool solution(vector<string> phone_book) {
	//bool answer = true;
	unordered_set<string> hash_set;
    
    for (auto& elem : phone_book)  hash_set.insert(elem);

	sort(phone_book.begin(), phone_book.end(),cmp);
	
	for (int i = 0; i < phone_book.size(); i++) {
        string str = "";
        
        // 중복 문자는 없으니 i번째 phone_book.size() -1 까지랑 비교하면 된다. 
        for(int j=0;j<phone_book[i].size()-1;j++){ 
            str += phone_book[i][j];
            if(hash_set.find(str) != hash_set.end()) return false;
        }
	}

	return true;
}

 

---

[ Key Point ]

 

👉 substr 함수가 O(n)의 시간복잡도를 가진다는것을 알았다.

 

👉 unordered_set 의 erase 는 3가지 형태가 있는데,

(2) 번  size_type erase( const key_type& k) 는 erase 한 개수를 리턴하기 때문에 

itr = erase(key) 가 안된다.  ( 주의하자. 이것 때문에 시간 많이 썻다.)

by position (1)	
iterator erase ( const_iterator position );
by key (2)	
size_type erase ( const key_type& k );  // erase 한 개수 리턴.
range (3)	
iterator erase ( const_iterator first, const_iterator last );

---

[ 다른 사람 풀이 ]

 

ref :: https://ansohxxn.github.io/programmers/kit2/

ref ::