[프로그래머스 42577] 전화번호 목록 / C++

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

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

string::find 는 실패시 std::string::npos 를 리턴

찾은 경우는 position을 리턴한다.

따라서 0이라면 prefix를 찾은것

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

using namespace std;

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

	std::sort(phone_book.begin(), phone_book.end());

	for (int i=0;i<phone_book.size()-1;i++)
	{
		auto keyword = phone_book[i];
		auto next = phone_book[i+1];

		if (keyword == next.substr(0, keyword.length()))
		{
			return false;
		}
	}

	return answer;
}

- 결국 sort 를 하게 되면 바로 다음 원소와만 비교하면된다

- 다음 원소의 접두어가 아니라면 그 뒤에 원소들은 비교할 필요도 없다 ( 이미 정렬되어 있으니..)

 

---

 

다른 사람 풀이

 

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

 

문제의도가 잘 반영된듯하다.

unodered_map<string, int> hash_map;

해시맵에 플래그를 사용하는 방식