프로그래머스 전화번호 목록(c++)

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

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

 

-문제 접근 방법

1) 사전순 정렬

처음에는 이중 for 문을 돌려 선형 탐색을 하면서 비교하여 문제를 해결했다.

정확도 테스트는 모두 통과했으나 효율성 테스트에서 통과하지 못했다.

 

그래서 더 좋은 방법이 있을지 고민하다 사전순 정렬을 떠올렸다.

 

string 타입의 선형 자료구조를 정렬할 시 사전 순으로 정렬된다.

 

즉 string 배열에 "119" "1180" "11900"로 정장 돼있을 경우
이를 정렬하면 "119" "11900" "1180"순으로 정렬된다.

 

phone_book 배열은 사전임으로 바로 인접한 인덱스와 비교만 하면 문제를 해결할 수 있다.


*다음다음 인덱스와는 비교를 안 하는 이유는(인접한 인덱스만 비교하는 이유)?

phone_book 배열은 사전 순으로 정렬됐기 때문에

i를 기준으로 i+2, i+3, i+4..... 들은 i+1보다 사전 순으로 크거나 같은 경우이다.

같다면 i+1에서 이미 false임을 알았을 겄이고 i+1이 false가 아닌 경우 

 

i가 "119"라면 i+1은 적어도 "120xxxxxx"일 것이다.

그럼으로 i+2이상의 수들도 적어도 "120xxxxxx"일 것이기 때문에 고려 할 필요가 없다.

 

 

 

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

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