Lv2_[전화번호 목록, C++] 풀이 및 알고리즘 정리 - 프로그래머스

 

프로그래머스

문제 내용, 조건, 예시는 프로그래머스 사이트 참조

---

'한 번호가 다른 번호의 접두어인 경우'를 찾아야하기 때문에 아래와 같은 생각을 했습니다.
"길이가 짧은 것을 앞에 배치하고 크기에 따라 정렬하면 편하겠다" 

위의 내용을 감안하여 알고리즘을 짜봤습니다.

알고리즘

1. sort 오름차순 정렬을 통해서 크기가 작은 값을 앞에 배치
   • ("234" < "1234") string 비교는 길이 짧은것이 작다고 판단, 길이가 같으면 크기 순으로 정렬)
2. 정렬된 순서대로 인접한 두 문자열을 비교
   •  비교할 때는 작은 문자열 기준으로 크기를 맞춰서 비교
3. 두 문자열 비교
   1. 일치하면 false 반환
   2. 일치하지 않으면 index+1 후 반복

 

#include <string>
#include <map>
#include <vector>
#include <algorithm>
 
using namespace std;
 
bool solution(vector<string> phone_book) {
    bool answer = true;
 
    sort(phone_book.begin(), phone_book.end());
    for(int i = 0; i < phone_book.size()-1; i++) {
        string a(phone_book[i]);
        string b(phone_book[i+1]);
        string comStr_1;
        string comStr_2;
 
        if(a.size() > b.size()) {
            comStr_1 = b;
            comStr_2 = string(a.begin(), a.begin()+b.size());
        } else {
            comStr_1 = a;
            comStr_2 = string(b.begin(), b.begin()+a.size());
        }
        
        if(comStr_1.compare(comStr_2) == 0) {
            answer = false;
            break;
        }
    }
 
    return answer;
}

 

↓↓↓↓↓↓ 유익했다면 하트 뿅 ♥ ↓↓↓↓↓↓