[프로그래머스 - level2] [해시] 전화번호 목록

문제 설명

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

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

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

제한 사항

• phone_book의 길이는 1 이상 1,000,000 이하입니다.
  • 각 전화번호의 길이는 1 이상 20 이하입니다.
  • 같은 전화번호가 중복해서 들어있지 않습니다.

입출력 예제

phone_book	return
["119", "97674223", "1195524421"]	false
["123","456","789"]	true
["12","123","1235","567","88"]	false

입출력 예 설명

입출력 예 #1
앞에서 설명한 예와 같습니다.

입출력 예 #2
한 번호가 다른 번호의 접두사인 경우가 없으므로, 답은 true입니다.

입출력 예 #3
첫 번째 전화번호, “12”가 두 번째 전화번호 “123”의 접두사입니다. 따라서 답은 false입니다.

 

---

 

처음에 시도한 풀이 과정

1. phone_book 벡터를 오름차순으로 정렬

2. phone_book.begin() 을 포함한 다음 원소들이 있는지 검사

 

 

처음에 시도한 오답 코드

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

using namespace std;

bool solution(vector<string> phone_book) {
    sort(phone_book.begin(), phone_book.end());
	string comp = *phone_book.begin();
	bool answer = true;
	for (auto iter = phone_book.begin() + 1; iter != phone_book.end(); ++iter) { // +1을 해줘야 begin()부분이랑 비교해서 무조건 false를 리턴하는 결과를 막는다
		if ((*iter).find(comp) != string::npos) {
			answer = false;
			return answer;
		}
	}
	return answer;
}

-> ["934793", "34", "44", "9347"] 과 같은 케이스에서 틀린값을 출력한다. 

 1. 이 벡터를 오름차순으로 정렬하면 34,44,9347,934793이 될텐데 그럼 비교하려는 문자열은 34가 되고 접두어를 찾기 위한 문자열이 아니다.

 2. find()함수는 해당 문자열이 시작되는 인덱스를 반환하는데 접두어를 찾기 위해서는 반환하는 인덱스가 0이 되어야 한다.

 

 

알게된 것

1. c++ string의 문자열 포함 검사 멤버함수는 find("string")이다 

 - e.g.) string str; str.find("abc");

 - 반환값은 찾는 문자열의 첫 번째 인덱스 값

 - 찾는 문자가 없을 경우는 string::npos를 리턴한다. (npos는 no position으로 쓰레기값 나옴)

 

---

 

다시 풀어본 풀이 과정

1. phone_book 벡터를 오름차순으로 정렬

2. 인접 원소끼리 비교해서 접두어가 있는지 검사

 

다시 풀어본 정답 코드

bool solution(vector<string> phone_book) {
	sort(phone_book.begin(), phone_book.end());
	bool answer = true;
	for (auto iter = phone_book.begin(); iter != phone_book.end(); ++iter) {
		if (iter != phone_book.end() - 1) {
			if ((*(iter + 1)).find(*iter) == 0) {
				answer = false;
				return answer;
			}
		}
	}
	return answer;
}

 

해시를 이용해 풀지는 않아서 다음에 해시맵을 이용해서 다시 한번 풀어보자