[백준 5052] 전화번호 목록(20200514 수정)

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

5052번: 전화번호 목록

 

 

요구사항

주어진 숫자가 일관성이 있는지 없는지 확인한다

 

풀이

1. 일관성이 있는지 비교하기 위해 주어진 숫자를 숫자가 아닌 문자열 입력으로 받는다

2. 문자열을 오름차순으로 정렬한다

3. 앞의 문자열이 뒤의 문자열과 일관성이 있는지 확인한다.

 

정렬 풀이

#include <stdio.h>
#include <algorithm>
#include <list>
#include <iostream>

using namespace std;
 
struct NODE {
    int prev;
    int next;
    int val;
};
const int MAX = 1000000+1;
char map[MAX][15];
char buf[MAX][15];
void strcmp(char a[], char b[]){
    int i=0,j=0;
    while(b[i]){
        a[i]=b[i];
        i++;
    }
    a[i]=0;
}
void mer(char arr[][15],int len){
   // cout<<len<<endl;
    if(len<2){
        return;
    }
    int i,j,mid,k;
    i=0;
    mid=len/2;
    j=mid;
    k=0;
    mer(arr,mid);
    mer(arr+mid,len-mid);

    while(i<mid && j<len){
    //    cout<<"A "<<i<<" "<<j<<endl;
        int z=0;
        int flag=0;
        for(z=0 ; arr[i][z]!=0 ; z++)
        {
       //     cout<<"!!!"<<endl;
            if(arr[i][z] < arr[j][z]){
                strcmp(buf[k++],arr[i++]);
                flag=1;
                break;
            }
            else if(arr[i][z]==arr[j][z])
            {
         //       cout<<"#E"<<endl;
                continue;
            }
            else
            {
                strcmp(buf[k++],arr[j++]);
                flag=1;
                break;
            }
        }
        if(flag==0)
        {
        if(arr[i][z] < arr[j][z]){
            strcmp(buf[k++],arr[i++]);
        }
        else{
            strcmp(buf[k++],arr[j++]);
        }
        }
    //    cout<<"B"<<endl;

    }
    while(i<mid){
        strcmp(buf[k++],arr[i++]);
    }
    while(j<len){
        strcmp(buf[k++],arr[j++]);
    }

    for(int i=0 ; i <len ; i++){
        strcmp(arr[i],buf[i]);
    }

}
int n;
int main(){
    int t;
    scanf("%d",&t);
    for(int tc=1;tc<=t;tc++){
        int flag=0;
        scanf("%d",&n);
        for(int i=0 ; i < n ; i++){
            scanf(" %s",map[i]);
        }
       mer(map,n);
       for(int i=0 ; i < n ; i++){
           int s=0;
           while(map[i][s]){
               s++;
           }
           int cnt=0;
           while(map[i][cnt]){
               if(map[i][cnt] ==map[i+1][cnt])
                {    cnt++;}
                else
                {
                    break;
                }
           }
           if(s==cnt)
            flag=1;
       }
       if(flag==1)
       {
           printf("NO\n");
       }
       else{
           printf("YES\n");
       }

    }
}

 

풀이

1. 입력을 map에 다 넣는다

2. 모든 index를 처음부터 탐색하여 접두사에 해당하는지 확인한다

 

해시 풀이(프로그래머스)

#include <string>
#include <vector>
#include <map>
#include <iostream>
#include <algorithm>
using namespace std;

bool solution(vector<string> phone_book) {
    bool answer = true;
    map<string, int> m;
    int flag = 0;
    for (auto i : phone_book) {
        string temp;
        if (flag == 1)
            continue;
        if (m[i] != 0) {
            flag = 1;
            break;
        }
        else {
            m[i]++;
        }
    }
    if (flag == 0) {
        for (auto i : phone_book) {
            string temp;
            if (flag == 1)
                continue;
            for (int j = 0; j < i.size() - 1; j++) {
                temp += i[j];
                if (m[temp] != 0) {
                    flag = 1;
                    break;
                }
            }

        }
    }
    if (flag == 1) {
        answer = false;
    }

    sort(phone_book.begin(), phone_book.end());
    for (auto i : phone_book) {
        cout << i << endl;
    }
    return answer;
}