5052번 - 전화번호 목록(c++)

🗒 5052번 문제

📌 해당 string이 전에 있던 string에 존재하는지 확인 ❗️

1️⃣ 앞에 있는 전화번호가 다른 전화번호의 접두어가 되면 안된다
-> 접두어가 있는지 find함수를 통해서 찾아내기

2️⃣ find함수는 해당 string이 find()속의 string에 포함되어 있으면 0를 출력하는 함수다.
-> 따라서 배열을 string으로 받아야 한다.

3️⃣ 받은 string은 sort를 통해서 정렬하는데 그 이유는 중첩 for문을 쓰지 않고 접두어가 되는 string를 찾아내기 위해서다
-> 🚨 실제로 시간 초과문제가 해당 부분에서 발생한다
-> sort된 배열은 앞, 뒤로 접두어를 찾지 않아도 되고 앞에 접두어가 있는지만 찾으면 되기에 for문을 중첩하지 않아도 됨

4️⃣ 만약 false가 전달되면 NO가 true가 전달되면 YES가 출력되도록 한다.

5️⃣ 배열은 num까지만 계속 사용하기 때문에 초기화하지 않았다
-> 🚨 memset 함수를 사용해서 초기화할 경우에는 런타임 에러가 발생한다

⭐️ 시간 초과, 런타임 에러 문제 조심하기
⭐️ string 으로 받지 않고 int을 사용할 경우에는 9999999999 해당 숫자가 들어오는 문제 조심하기

➰ 코드로 나타낸 5052번 ➰

#include <iostream>
#include <algorithm>

using namespace std;

int testcase, num = 0;
string telephones[10002];

bool testConsistency() {
    for (int i = 0; i < num; i++)
        cin >> telephones[i];
    
    sort(telephones, telephones+num);
    
    for (int i = 1; i < num; i++) {
    	// 정렬을 이미 해서 앞부분의 값이 내 string과 접두어 관계인지만 보면 됨
        if (telephones[i].find(telephones[i - 1]) == 0) return false;
    }
    
    return true;
}

int main() {
    cin >> testcase;
    
    while(testcase--) {
        cin >> num;
        
        if(testConsistency()) cout << "YES" << endl;
        else cout << "NO" << endl;
    }
}