[백준(BOJ)] 5052번 전화번호 목록 C++

문제 : https://www.acmicpc.net/problem/5052

5052번: 전화번호 목록

어떤 문제인가?

전화번호 목록에 여러 개의 전화번호가 존재한다.

문제의 예시처럼 선영이에게 전화를 걸기 위해선 911을 눌러야 하지만 911이란 번호가 긴급전화라 전화 버튼을 누르지 않아도 바로 전화가 걸린다.

따라서 선영이에게 전화를 거는 것은 불가능하다. 이러한 전화번호 목록을 일관성이 없다고 문제에서 표현했다.

 

문제는 어떠한 전화번호 목록이 일관성이 있는지 없는지의 여부를 묻는 문제이다.

 

 

접근 방법

접두어라는 말에 집중해야한다.

만약에 길이가 4, 5인 번호가 있다.

이때 길이가 5인 번호는 4인 번호의 접두어가 될 수 없다.

길이가 더 길기 때문이다.

 

int t, n;
cin >> t;

while (t--) {
    vector<string> number;
    cin >> n;

    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        number.push_back(s);
    }

 

변수들을 입력받고 전화번호들을 저장할 벡터를 선언한다.

전화번호를 n번만큼 입력받고 벡터에 추가해준다.

 

sort(number.begin(), number.end());

사실 이 부분을 생각해내는 것이 이 문제 해결에 가장 중요한 부분이라고 생각한다.

입력받은 전화번호들을 오름차순으로 정렬해준다.

정렬하게 된다면 벡터의 앞에서부터 비교를 해나갈 수 있게 된다.

 

 

bool possible = true;

 

일관성 여부를 나타내 줄 변수를 선언해준다.

 

for (int i = 0; i < n - 1; i++) {

    if (number[i].length() > number[i + 1].length()) {
        continue;
    }

    if (number[i] == number[i + 1].substr(0, number[i].length())) {
        cout << "NO\n";
        possible = false;
        break;
    }
}

i번째 번호와 i+1번째 번호를 비교할 것이기 때문에 반복문은 n-1번 반복한다.

 

그리고 i번째 번호가 i+1번째 번호보다 길이가 길다면 위에서 설명했듯이 그냥 넘어간다.

 

만약 i번째 번호가 i+1번째 번호의 접두어라면 NO를 출력해준다.

이때 substr을 쓰는 이유는"접두어"이기 때문에 i+1번째 번호의 0번 인덱스부터 i번째 번호의 길이만큼의 인덱스만 보면 된다.

 

if (possible) {
    cout << "YES\n";
}

마지막으로 가능하다면 YES 출력!

 

무엇이 어려웠는가?

먼저 sort를 통해 정렬을 할 생각을 하는 것이 매끄럽지 못했다.

왜냐하면 나는 접두어라는 것에 포커스를 두지 않았다.

문자열 폭발 문제 처럼 그냥 한 번호에 다른 번호가 포함되어있으면 안된다고 생각했다.

 

다시 생각해보니

911

123911 이란 번호가 있을 때는 상관이 없는 일이었다.

 

그래서 find로 번호를 찾는 것이 아니라 substr을 사용할 수 있었다.

 

문제를 제대로 이해하고 나니 쉽게 풀 수 있었다.

 

배운 점

문제를 제대로 읽고 제대로 이해하는 것이 정말 중요하다.

아무리 훌륭한 구현을 했더라도 문제에서 요구한 대답이 아니면 아무 쓸모가 없는  것이다.

문제를 제대로 이해할 수 있도록 노력해야겠다!!