[고득점Kit][해시] 전화번호 목록 (unordered_set, 테케 추가 후 다시 풀이) ⭐⭐

Date: 2020.07.17 Updated: 2021.03.25

카테고리: Programmers

태그: Coding Test Hash Algorithm

[해시] 전화번호 목록

난이도 ⭐⭐

⭕

문제

내 풀이

이전 풀이 (예전엔 정답이었지만 이젠 ⏰시간초과 나는 풀이)

#include <string>
#include <vector>
#include <map>

using namespace std;

bool solution(vector<string> phone_book) {
	bool answer = true;

	map<string, int> strMap;

	for (auto & elem : phone_book)
	{
		if (strMap.find(elem) == strMap.end())
		{
			int size = elem.length();
			strMap.insert(make_pair(elem, elem.length()));
		}
		else
		{
			answer = false;  // 완전히 동일한 경우
			return answer;
		}
	}

	for (auto & elem : strMap)
	{
		for (auto itr = ++strMap.find(elem.first); itr != strMap.end(); itr++)
		{
            if(elem.second > itr->second)
                    continue;
            
            bool flag = true;
			for (int i = 0; i < elem.second; i++)
			{
				if (elem.first[i] != itr->first[i])
				{
					flag = false;
				}
			}
            if (flag == true)
            {
                answer = false;
                return answer;
            }
		}
	}

	return answer;
}

이 풀이는 시간 초과가 발생하는 풀이입니다. (2021-03-04 전에는 통과되던 풀이였지만 이제는 통과되지 않습니다.)

문자열들이 정렬되야 한다고 생각했다. ⭕
- 정렬되야 같은 문자인지 앞 원소부터 비교가 쉽기 때문에!
  - 정수로 정렬하면 35가 1232보다 앞에 있지만 문자열로 정렬하면 “1232”가 “35”보다 앞에 있게 된다.
- 그러나 이 문제가 ‘해시’로 분류되어 있는 만큼 Hash map 으로 풀어야 한다는 강박관념에 ㅠㅠㅠ map 컨테이너를 선택했다. 🔺 (근데 생각해보니까 그냥 map은 hash map 아니자나… unordered_map이 해시맵이잖아…)
  - map 컨테이너는 원소들이 ‘Key’를 기준으로 정렬되어 저장되기 때문이다.
    - 그러나 꼭 map 컨테이너 쓸 필요 없이 그냥 인수로 들어오는 vector 컨테이너를 정렬해서 사용하면 더 간단할 수 있었다.
  - 맵 컨테이너에 phone_book 벡터의 문자열 원소를 key로, 원소인 문자열의 길이를 value로 함께 묶어 insert 하였다.
    - 문자열의 길이를 value로 설정한 이유
      - 다른 문자열과 접두사가 같은지 검사할때 딱 그 value 개수만큼만 앞부터 검사하면 되기 때문.
      - 또한 비교하려는 문자열의 길이보다 크면 어차피 다르므로 비교할 필요가 없다. 이렇게 거를 때도 사용하려고.
  - 만약 기존 맵 컨테이너에 동일한 Key가 이미 있다면 answer = false 를 리턴하고 종료한다.
    - “abc”, “abc” 이렇게 완전히 동일한 경우가 해당.
삼중 for문 좀 극혐이지만 완전히 다 세제곱으로 돌지 않고 금방 리턴 될 수 있기 때문에 문제 없을거라고 판단함.
- for (auto itr = ++strMap.find(elem.first); itr != strMap.end(); itr++)
- 맵 컨테이너의 현재 원소인 elem(pair)와 그 다음 원소들(itr이 순회하며 가리킬것)과 접두사 비교
  - itr이 가리키는 원소의 Key(문자열)이 elem의 Key(문자열)을 맨앞부터 완전히 포함하는지를 보면 된다.
    - 완전히 포함하면 접두사가 같은것이 존재하는 것이므로 answer = false를 리턴하고 종료해야 한다.
  - 세번째 for문인 for (int i = 0; i < elem.second; i++) 에서 두 문자열의 문자 하나씩 검사한다.
    - elem의 Key(문자열)을 완전히 포함하는지 검사하는 것이므로 elem.second 즉 문자열 길이만큼만 반복하면 된다.
    - 하나라도 다른게 있었으면 flag는 false가 됨.
    - 전부 같았으면 flag 는 true로 유지될 것이므로 같은게 존재하는 것이니 answer = false를 리턴하고 종료.
    - 모든 elem들에 대해서 단한번도 이 if에 걸리지 않았다면 answer는 true로 유지되어 마지막에 return true 하게 된다.

8 개월 후 다시 푼 풀이 ⭕ (2021-03-25 업데이트)⭐

2021-03-25 추가

우연히 이 문제 페이지에 들어갔다가 이 문구를 발견하였다. 아니나 다를까 내가 위에 작성한 풀이는 이제 효율성 테스트에서 시간초과가 발생하여 통과되지 못하는 풀이가 되버렸다. 그래서 이왕 이렇게 발견한김에 다시 한번 이 문제를 풀어보았다!

#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; // 한번도 리턴되지 못했다면 접두어 번호가 없는 것이다.
}

phone_book의 최대 길이는 1,000,000 백만이기 때문에 이 문제의 시간복잡도는 O(NlogN)을 넘어선 안된다. 즉, 절대 O(N^2)이 되선 안된다. 또한, 딱히 (Key, Value) 가 필요하진 않고 그저 해시맵에 이 단어가 존재하는지만 볼 것이기 때문에 unordered_set 을 사용하였다.

단어 하나하나를 해시맵에 등록해두고 검색도 해시맵에서 하기 때문에 이전 인덱스들에 해당하는 구간을 다시 순회할 필요가 없다! 심지어 해시맵 검색은 훨씬 더 빠르다.(상수 시간에 가깝다고 알고 있음)

phone_book을 정렬하여 접두어가 될 수 있는 번호가 최대한 앞에 오도록 한다. (문자열 정렬 기준으로는 “12”가 “123”보다 앞에 온다.)
- 이 정렬 과정 때문에 O(NlogN)
phone_book 문자열 하나 하나 순회하기 👉 O(N)
- 1️⃣ 접두어가 있는지 확인 (예를 들어 “abc”라면 “a”, “ab”, “abc” 모두 해시맵에 이미 있는지 검사한다.)
  - phone_book[0]은 검사할게 없으니 미리 2️⃣ 과정에 해당하는 해시맵에 추가만 해주고 시작했다.
  - 해시맵에 있다면 접두어가 번호로서 기존에 존재했다는 것이므로 바로 false 리턴 후 종료
- 2️⃣ 해시맵에 등록
  - 한번도 접두어가 없어 리턴되지 못했다면 phone_book[i]이 어떤 단어의 접두어가 될 수도 있으니 phone_book[i]을 해시맵에 등록한다.

이 문제는 프로그래머스에서 내가 두 번째로 풀었던 문제로, STL에 대해서도 잘 모르던 코테 왕초보일 때 풀었던 문제이다. 다시 풀어야겠다 마음 먹고 바로 코드 쓰고 채점까지 3 분도 안걸렸던 것 같은데 이 문제를 처음 풀이했을 땐 굉장히 고민을 많이 했었던게 기억이 난다. 내 옛날 풀이를 보니 phone_book 최대 길이가 백 만인데 이렇게 풀면 안되지!! 싶은 생각이 든다.. 지금도 멀었긴 한데..ㅋㅋㅋ 새삼 그동안 실력이 많이 늘었구나 싶다.

여러 답안

vector & 문자열 비교시 string 함수 사용

#include <string>
#include <vector>
#include <iostream>
#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(); i++){
        for(int j=i+1; j<phone_book.size(); j++) {
            if(phone_book[j].find(phone_book[i]) != string::npos) {
                return false;
            }
        }
    }
    return answer;
}

sort로 string 벡터를 정렬해준 후 j = i+1 부터 검사
std::string의 find함수
- phone_book[j].find(phone_book[i])
- phone_book[j] 문자열 내에서 phone_book[i] 문자열이 포함되있을 경우 이 위치를 리턴. 없을 경우 -1 리턴

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

이중 for문 쓸 필요없이 하나의 for문으로 이웃 끼리 비교
- 정렬 되있으니까 가능한 것
std::string의 substr함수
- phone_book[i]과 정렬된 그 다음 순서인 phone_book[i + 1]의 0번째부터 phone_book[i]길이 까지의 부분 문자열이 같은지 검사

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

using namespace std;

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

이중 for문 쓸 필요없이 하나의 for문으로 이웃 끼리 비교
- 정렬 되있으니까 가능한 것
std::string의 to_string함수, stoi함수
- to_string함수 : 문자열로 변환
- stoi함수 : 문자열을 정수로 변환
- ex) i -> “123”, i + 1 -> “1234”
  - 123+1이 되는 “124”가 “1234”보다 크다.
    - if 조건문이 true가 되므로 return false
  - i+1 문자열이 i 문자열을 접두사로 포함했다면 i를 1증가시켯을때 i + 1보다 커졌을 것이다.
- ex) i -> “123”, i + 1 ->”125”
  - 123+1이 되는 “124”가 “125” 보다 작다.
  - i+1 문자열이 i 문자열을 접두사로 포함하지 않았다면 i를 1 증가시켜도 i+1 보다 작거나 같았을 것이다.
- 이 모든게 정렬시켜놨다는 가정이 있기에 가능한 것.

hash map 사용

unordered map

#include <string>
#include <vector>
#include <unordered_map>

using namespace std;

bool solution(vector<string> phone_book) {
    bool answer = true;

    unordered_map<string, int> hash_map;
    for(int i = 0; i < phone_book.size(); i++)
        hash_map[phone_book[i]] = 1;

    for(int i = 0; i < phone_book.size(); i++) {
        string phone_number = "";
        for(int j = 0; j < phone_book[i].size(); j++) {
            phone_number += phone_book[i][j];
            if(hash_map[phone_number] && phone_number != phone_book[i])
                answer = false;
        }
    }

    return answer;
}

unordered_map 컨테이너
1. 정렬 X
2. 중복 Key X
후에 논리 연산을 위해 value를 1로 하여 문자열 벡터 원소들을 모두 hash map 에 추가한다.
벡터의 i 번째 원소마다 임시 문자열 phone_number에 원소 문자열 길이 동안만 한 문자씩 phone_number에 붙인다.
- phone_number += phone_book[i][j];
- 한문자씩 붙일 때마다 그 문자열이 되는 원소가 있는지 검사
  - ex) [“12”, “1234”, “78”]
    - i = 0, j = 0 일때 phone_book[i]= “12”
      - phone_number = “1”
      - “1”은 해시맵에 없고([]로 참조했을때 없을시 0 리턴) && “1”은 “12”가 아님
        
        if문 false (“1”이 해시맵에 없어서)
    - i = 0, j = 1 일때 phone_book[i]= “12”
      - phone_number = “12”
      - “12”은 해시맵에 있는데 && “12”은 “12”임. 원소 자기 자신끼리 한 셈이라서 무효
        
        if문 false (원소 자기 자신끼리 한 셈이라서)
        
        unordered_map 컨테이너는 중복 Key를 허용하지 않으므로 문자열(Key)이 같으면 자기 자신인거다.
    - i = 1, j = 1 일 때 phone_book[i]= “1234”
      - phone_number = “12”
      - “12”은 해시맵에 있고 && “12”은 “1234” 와 다름.
        
        1234의 12 접두사가 해시맵에 있다는 얘기이므로 if 조건 true.

🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우 
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄

맨 위로 이동하기

공부하는 식빵맘 👱‍♀️