하루하루 꾸준히, 인생은 되는대로

자료구조

백준 전화번호 목록 C++

긤효중 2022. 3. 17. 02:32

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

 

5052번: 전화번호 목록

첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1 ≤ n ≤ 10000) 다음 n개의 줄에는 목록에 포함되어 있는 전화번호가

www.acmicpc.net


문제

전화번호 목록이 주어진다. 이때, 이 목록이 일관성이 있는지 없는지를 구하는 프로그램을 작성하시오.

전화번호 목록이 일관성을 유지하려면, 한 번호가 다른 번호의 접두어인 경우가 없어야 한다.

예를 들어, 전화번호 목록이 아래와 같은 경우를 생각해보자

  • 긴급전화: 911
  • 상근: 97 625 999
  • 선영: 91 12 54 26

이 경우에 선영이에게 전화를 걸 수 있는 방법이 없다. 전화기를 들고 선영이 번호의 처음 세 자리를 누르는 순간 바로 긴급전화가 걸리기 때문이다. 따라서, 이 목록은 일관성이 없는 목록이다. 


입력

첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1 ≤ n ≤ 10000) 다음 n개의 줄에는 목록에 포함되어 있는 전화번호가 하나씩 주어진다. 전화번호의 길이는 길어야 10자리이며, 목록에 있는 두 전화번호가 같은 경우는 없다.


출력

각 테스트 케이스에 대해서, 일관성 있는 목록인 경우에는 YES, 아닌 경우에는 NO를 출력한다.


9 1 1          
9 7 6 2 5 9 9 9
9 1 1 2 5 4 2 6
  • 긴급전화: 911
  • 상근: 97 625 999
  • 선영: 91 12 54 26 의 경우에 상근은 선영에게 전화를 걸 수 없다 (전화를 걸면 긴급전화가 걸리기 때문)

91125426의 접두어 -> 911

 

처음 생각한 방법

->문자열 배열에 911,97625999,91125426을 모두 넣고 이중 for문 돌리면서 두 문자열이 같으면 일관성 X인 경우이므로 시도해봤지만 실패/..

 

구글링 후 정렬을 사용해야 한다는 사실을 알 수 있었다..!

 

 

시간복잡도에 안걸리는 방법->정렬을 사용한다..

기존의 긴급전화,상근,선영을 정렬한다면 (오름차순정렬)

 

9 1 1          
9 1 1 2 5 4 2 6
9 7 6 2 5 9 9 9

이렇게 바뀐다.

 

정렬 후 알수있는 사실은 문자열 A가 문자열 B의 접두사가 된다면 문자열 B는 문자열 바로 A뒤에 온다.

 

예를 들어 "abbb" , "abbbc", "abbbccd" 의 경우 정렬을 한다면 

"abbb"

"abbbc"

"abbbccd" 이런 순으로 오게 되는데 "abbbc"가 "abbb"의 접두사가 된다면 "abbbc"는 "abbb"의 바로 뒤에 온다.

 

이렇게 정렬을 한 후 

 

911,91125426,97625999를 for문 한번만 돌게 하면 된다.

 

배열의 i번쨰 문자열과 배열의 i+1 문자열을 비교하는데 오름차순 정렬이 된 후 이므로 배열의 i+1문자열을 i번째 문자열의 크기만큼 비교하면 된다.


새롭게 알게 된 사실: C++에서 문자열의 부분문자열을 추출할떄 substr을 사용하자.

string substr (size_t pos = 0, size_t len = npos) const

 

시작(pos)지점과 길이를 입력받아서 부분문자열을 리턴한다.

 

ex) (0~3)까지의 부분문자열을 리턴받고 싶을떄

string str = "Hello_world"

str.substr(0,3)


시간초과 코드 

->

#include <iostream>
#include <map>
#include <string>
 
using namespace std;
 
bool compare(string a,string b){
    int num1 = a.size();
    int num2 = b.size();
    return num1 < num2;
}
 
int main(void){
   int t;
   cin >> t;
 
    for(int i = 0;i<t;i++){
         string arr[10000];
         int n;
         cin >> n;
        for(int j = 0;j<n;j++){
             cin >> arr[j];
        }
        bool is_not_correct = false;
        for(int j = 0;j<n;j++){
            for(int q = j+1;q<n;q++){
                if(arr[q].find(arr[j]) != string :: npos){
                    is_not_correct = true;
                    break;
                }
                   else{
                       continue;
                   }
            }
             if(is_not_correct == true){
                       break;
                   }
        }
 
                   if(is_not_correct == true){
                       cout << "NO" << '\n';
                   }
                   else{
                       cout << "YES" << '\n';
                   }
 
 
}
 
}

정답 코드->

#include <iostream>
#include <string>
#include <algorithm>
 
using namespace std;
 
int main(void){
 
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
   int t;
   cin >> t;
 
   for(int i = 0;i<t;i++){
       bool is_not_correct = false;
         string arr[10000];
         int n;
         cin >> n;
        for(int j = 0;j<n;j++){
             cin >> arr[j];
        }
       sort(arr,arr+n); //사전순으로 정렬하기
 
       for(int j = 0;j<n;j++){
           string temp = arr[j]; //J번쨰 배열의 문자열
           string temp_2 = arr[j+1].substr(0,temp.size());
           //J+1배열의 문자열을 J번쨰 문자열 길이만큼 짤라놓고 비교
           
           if(temp == temp_2){ //J와 J+1배열의 문자열이 같다면
               is_not_correct = true; //일관성이 없는 경우 ->is_not_correct변수를 true로 바꿔주기
               break;
           }
           else{
                continue;
           }
       }
 
 
 
       if(is_not_correct == true){ //is_not_correct == true->일관성이 없는 경우
           cout << "NO" << '\n';
       }
       else{ //그 외의 경우 일관성이 있는 경우
           cout << "YES" << '\n';
       }
 
}
 
}

'자료구조' 카테고리의 다른 글

STD::multimap  (0) 2022.03.19
백준 1755 C++  (0) 2022.03.19
백준 걸그룹 마스터 준석이 C++  (0) 2022.03.12
백준 숫자 카드 2 C++  (0) 2022.03.09
C++ Map사용법 [STL] + 백준 듣보잡  (0) 2022.03.08