(프로그래머스 코딩테스트 고득점 kit) 해시 Level2 전화번호 목록
by 줌코딩
문제
전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다.
전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다.
- 구조대 : 119
- 박준영 : 97 674 223
- 지영석 : 11 9552 4421
전화번호부에 적힌 전화번호를 담은 배열 phone_book 이 solution 함수의 매개변수로 주어질 때, 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false를 그렇지 않으면 true를 return 하도록 solution 함수를 작성해주세요.
검색을 위해서 뭐를 써야하는가?(sorting?)
- 처음에는 사이즈로 작은 순으로 정렬을 하고 사이즈로 진행하려고 했다.
- size로 정렬하고 size가 작은 친구(i)부터 다른 친구(j)와 비교하려고 했다.
- 문자를 일일이 비교하려고 하니 for문이 하나 더 필요했다.
- 결과적으로 복잡도는 for문 3개로 n의 3승이 됐다…
- 당연히 정답은 모르겠는데 효율성 바닥으로 80점 맞았다.
sort 활용 코드(복잡도 : O(n^3))
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <iostream>
using namespace std;
bool compare(string a, string b){
return a.size()< b.size();
}
bool solution(vector<string> phone_book) {
for(int i = 0; i < phone_book.size(); i++){
cout<< i << ":"<< phone_book[i]<< endl;
}
int book_size = phone_book.size();
//sorting을 해서 넣어볼까?
for(int i = 0; i < phone_book.size(); i++){
//길이가 짧은 애들을 앞으로
sort(phone_book.begin(), phone_book.end(), compare);
}
// printf("%d\n", phone_book.size());
for(int i = 0; i< book_size; i++){
for(int j = i + 1; j < book_size; j++){
int k;
for(k = 0; k < phone_book[i].length(); k++){
// printf("i = %d, j = %d, k = %d\n", i, j, k);
// cout<<phone_book[i]<<endl;
// cout<<phone_book[j]<<endl;
if(phone_book[i].at(k) != phone_book[j].at(k)){
// cout << "pass"<< endl;
break;
}
}
// cout<<phone_book[i].length()<<endl;
// cout<<k<<endl;
if(k == phone_book[i].length()) {
// cout << "return false" << endl;
return false;
}
}
}
return true;
}
Search에는 역시 해쉬?
- 이번에는 해쉬를 이용했다.
- 해쉬의 key말고 value에 넣는게 의미가 없으니까 사실 해쉬를 쓰는게 맞나 라는 의문이 들었는데 일단 보자
- 처음에는 넣은 뒤에 vector을 sorting도 하면 빠르지 않을까 했는데 sorting 시간 때문에 fail!
- 다 빼고 해쉬에 넣고 해쉬에 있는지만 확인하는 식으로 가보자
- 확인할때 글자 개수를 이용해서 i길이 만큼의 substring을 생성
- 생성한 substring를 해쉬맵에 find해서 있으면 return false!
hashmap 활용 코드(복잡도 : O(n^2))
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <iostream>
using namespace std;
bool solution(vector<string> phone_book) {
int book_size = phone_book.size();
//max, min은 검색하는 for문을 위해서 만듬
map<string, int> m;
int max = 0;
int min = phone_book[0].length();
//해쉬맵에 넣어
for(int i = 0; i < phone_book.size(); i++){
int len = phone_book[i].length();
if(len > max) max = len;
if(len < min) min = len;
m.insert(make_pair(phone_book[i], 1) );
}
//글자수 만큼을 찾아
for(int i = min; i <= max; i++){
for(int j = 0; j < phone_book.size(); j++){
//string의 길이가 글자수보다 짧으면 패스
if(phone_book[j].length()<i) continue;
string x = phone_book[j].substr(0, i);
//substr이 string이랑 같으면 패스
if(x.compare(phone_book[j]) == 0) continue;
//해쉬맵에 존재하면 return false
if(m.find(x)->second == 1){
return false;
}
}
}
return true;
}
느낀점
- 해쉬맵의 value가 없더라도 효율을 위해서 쓸수있다.
- sorting을 하는 게 오히려 시간을 늘릴수도 있다.
- 나는 아직 많이 엄청 많이 부족하다
이 포스팅은 쿠팡 파트너스 활동의 일환으로, 이에 따른 일정액의 수수료를 제공받습니다.
Subscribe via RSS