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

 

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

 

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

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

---

 

해결전략

 

set, string

 

phone_book[i + 1].substr(0, phone_book[i].size())

 

basic_string substr(size_type start = 0, size_type count = nstart) const;

[start, start+ count)

문자열의 start 번째 문자부터 count 길이 만큼의 문자열 추출

 

---

 

처음 시도한 코드

 

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
 
vector<pair<int, int>> v;
 
string solution(vector<string> phone_book) {
    
    for(int i=0; i<phone_book.size(); i++){
        v.push_back({ phone_book[i].size(), stoi(phone_book[i]) });
    }
 
    sort(v.begin(), v.end());
 
    for(int i=1; i<v.size(); i++)
    {
	    for(int j=0; j<i; j++)
	    {
            int Isize = v[i].first; //더 큰 수 숫자개수
            int Jsize = v[j].first; //더 작은 수 숫자개수
            int dif = Isize - Jsize;
 
            int IfrontNum = v[i].second / (pow(10, dif));
 
            if (v[j].second == IfrontNum){
                return "false";
            }
	    }
    }
 
    return "true";
}

 

"segmentation fault (core dumped)" 오류 발생

1. "stoi 함수
   1. stoi 함수는 문자열을 정수로 변환하는 함수인데, 이 문자열에 숫자가 아닌 다른 문자가 포함되어 있거나 숫자의 범위가 int의 범위를 넘어갈 경우에 예외를 발생시킨다.
      
      여기서 phone_book 벡터에 들어있는 각 문자열은 전화번호를 나타내므로, 이들은 대체로 10자리 이상의 긴 숫자도 포함된다. 그런데 int의 최대 값은 약 21억(2,147,483,647)으로 10자리 미만이므로, 그보다 큰 수를 표현하려 할 때 오버플로우가 발생한다. 따라서 여기서 'stoi' 함수를 사용하면 문제가 생긴다.
2. 문제에서 주어진 bool solution()함수를 string solution()함수로 변환해서 문제가 생김.
   
   1. 문제에서 주어진대로 bool answer를 리턴해줘야 한다.  

 

---

 

 

두번째 시도한 코드  -  시간초과 

 

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
 
bool solution(vector<string> phone_book) {
    bool answer = true;
    
    vector<pair<int, string>> v; //전화번호 길이, 전화번호
    
    for(int i=0; i<phone_book.size(); i++){
        v.push_back({ phone_book[i].size(), phone_book[i] });
    }
 
    sort(v.begin(), v.end());
 
    for(int i=1; i<v.size(); i++)
    {
	    for(int j=0; j<i; j++)
	    {
            string IfrontNum = v[i].second.substr(0, v[j].first);//더 긴 전화번호를 더 짧은 전화번호 길이로 맞춰준다.
 
            if (v[j].second == IfrontNum){ // 더 짧은쪽 전화번호 == 더 긴 전화번호 접두사
                answer = false; 
                return answer;
            }
	    }
    }
    
    return answer;
}

 

 

이중 for문이 있어 시간복잡도가O(n^2)이어서 시간초과가 나온다.  

 

---

 

정답코드

 

#include <string>
#include <vector>
#include <algorithm>
using namespace std;
 
bool solution(vector<string> phone_book) {
 
    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 true;
}

 

 

1. sort 함수를 사용하여 전화번호를 사전 순으로 정렬.
2. 각 전화번호가 바로 다음 전화번호의 접두사인지 확인.
3. 만약 접두사라면, false를 반환하고 함수를 종료

정렬된 상태에서 한 번호가 다른 번호의 접두사라면, 그 두 번호는 서로 인접해 있다.

 

 

테스트 케이스가 vector<string> testcase3 = { "88", "12","1235","567","123", };라면

정렬 후