전화번호 목록

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
 
using namespace std;
 
bool solution(vector<string> phone_book) {
    if(phone_book.size() == 1) return true;
    int size = phone_book.size();
        
    for(int i = 0; i < size; i++) {
        int len = phone_book[i].length();
        for(int  j = 0; j < size; j++) {
            if(j == i) continue;
            int len2 = phone_book[j].length();
            if(len > len2) continue;
            else {
                string str = "";
                for(int k = 0; k < len; k++) {
                    str += phone_book[j][k];
                }
                if(phone_book[i].compare(str) == 0) return false;
            }
        }
    }
    return true;
}

문제를 이해해보면 길이가 짧은 것과 긴 것을 비교해서 긴 번호의 맨 앞자리에 짧은 번호가 포함되는지 아닌지를 판단하는 것이다.

문제는 간단하게 이해가 되지만 이것을 c++로 표현을 하기 위해서 많은 것을 써야하기에 이렇게 푸는 것이 맞는지 많이 고민을 했다. 하지만 더 좋은 방법이 떠오르지 않아서 일단 이런 조금 조잡해보이는 코드로 해결을 했다. 나중에 알고리즘을 좀 더 공부하고 괜찮은 방법이 나오면 또 다른 풀이가 나올 것이다.

문제 풀이를 해보면 처음에 인자로 받은 phone_book의 길이가 1이면 true를 반환한다. 그 이유는 이 번호와 같은 번호가 존재할리 없기 때문이다. 그리고나서 phone_book에 저장된 길이만큼 반복을 하면서 i에 해당하는 phone_book스트링의 길이를 저장한다. 그 이유는 뒤에 나오는 j에 해당하는 스트링 길이와 비교를 하여 i길이 값이 더 크면 그것은 비교를 할 수가 없기 때문이다. 다음으로 j반복문에 들어가서 처음에 j와 i가 같다면 그것은 무시하고 j값을 하나 증가시켜준다. 이유는 j와 i가 같다면 같은 문자를 비교하는 것이기 때문에 피해주는 것이다.

다음으로 앞에서 나온 조건이 아니라면 이제 i값과 j값을 비교한다. 그런데 이를 비교해주기 위해서는 j값에 해당하는 문자열 중 i값의 길이만큼의 스트링만 필요하다. 그래서 하는 작업이 else안의 for문이다. 현재 j값에 해당하는 스트링을 i값의 길이만큼만 비교하도록 임시 str변수에 저장하는 것이다.

마지막으로 str과 i값을 비교해서 같다면 false를 반환해주고 모두 비교했을 때 아직 반환이 되어 끝나지 않았다면 true를 반환해주면 된다.