프로그래머스 level2 연습 문제-전화번호 목록

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

코딩테스트 연습 - 전화번호 목록 | 프로그래머스

정답 : 

#include <string>
#include <vector>
#include<algorithm>
using namespace std;

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

 

 

200807

헤시를 이용해서 풀어보앗다 

 

#include <stdio.h>
#include <string.h>
#include <string>
#include <vector>
#include <unordered_map>
#include<iostream>
#include<cstring>

using namespace std;
unordered_map<int,string >data;
bool solution(vector<string> phone_book) {
    bool answer = true;
    for(int i=0;i<phone_book.size();i++)
        data[i]=phone_book[i];
    
    
    
    for(int i=0;i<phone_book.size();i++){
        for(int j=i+1;j<phone_book.size();j++){
            
         
       if (strncmp (data[i].c_str(),data[j].c_str(),data[i].length()) == 0)
        {
            return false;
        }
         if (strncmp (data[i].c_str(),data[j].c_str(),data[j].length()) == 0)
        {
            return false;
        }   
        }
        
        
    }
    
    return true;
}

 

 

여기서 문제가 데이터가 정렬되지 않아서 접두사가 뒤쪽이 더 길수도 있다

그래서 앞데이터 길이로 비교 뒷 데이터 길이로 비교 해줘야한다

if (strncmp (data[i].c_str(),data[j].c_str(),data[i].length()) == 0)
        {
            return false;
        }
         if (strncmp (data[i].c_str(),data[j].c_str(),data[j].length()) == 0)
        {
            return false;
        }   

그리고 여기서 strncmp가 문자열 string 비교이다. string data에다가는 .c_str()를 넣어줘야 비교 가 가능하다 

즉 strncmp(비교데이터1 ,비교데이터2 ,비교할 문자 갯수); 0이면 전부 동일하며 아니면 1로 반환을 한다.

 

201004

 

음 이게 해시를 사용하라는데 해시 사용에 의미가 있는건지 잘모르겟다. 

효율성 검사해서도 그냥 통과햇으니 뭐 

#include <string>
#include <vector>
#include<cstring>
using namespace std;

bool solution(vector<string> phone_book) {
    bool answer = true;
  
    
     for(int i=0;i<phone_book.size();i++){
        for(int j=i+1;j<phone_book.size();j++){
            
         
       if (strncmp (phone_book[i].c_str(),phone_book[j].c_str(),phone_book[i].length()) == 0)
        {
            return false;
        }
         if (strncmp (phone_book[i].c_str(),phone_book[j].c_str(),phone_book[j].length()) == 0)
        {
            return false;
        }   
        }
        
        
    }
    
    
    return answer;
}

그냥 문자열 비교만 하면 해결되는건데 흠 ..

효율성도 흠 그닥 1초 미만이고 과연 이 문제에서 해시의 사용 이유가 필요한가 해시의 문제라고 보긴 좀 어려운것같다.