[고득점Kit][해시] 전화번호 목록 ⭐⭐

C++로 풀이했습니다.
출처 : 프로그래머스 고득점 Kit 문제 풀이. https://programmers.co.kr/learn/challenges

[해시] 전화번호 목록

난이도 ⭐⭐

⭕

문제

전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다.
전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다.

구조대 : 119
박준영 : 97 674 223
지영석 : 11 9552 4421

전화번호부에 적힌 전화번호를 담은 배열 phone_book 이 solution 함수의 매개변수로 주어질 때, 
어떤 번호가 다른 번호의 접두어인 경우가 있으면 false를 
그렇지 않으면 true를 return 하도록 solution 함수를 작성해주세요.

📢 제한사항

- phone_book의 길이는 1 이상 1,000,000 이하입니다.
- 각 전화번호의 길이는 1 이상 20 이하입니다.

내 풀이 & 내 생각 : map 사용

#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;
}

• 문자열들이 정렬되야 한다고 생각했다. ⭕
  • 정렬되야 같은 문자인지 앞 원소부터 비교가 쉽기 때문에!
    • 정수로 정렬하면 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 하게 된다.

여러 답안

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.

---

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

맨 위로 이동하기