접두사 > 문제은행



알고리즘 문자열

1885 : 접두사

제한시간: 2000 ms    메모리제한: 512 MB
해결횟수: 135 회    시도횟수: 696 회   



주어진 숫자 배열에서 임의의 어떤 숫자가 다른 숫자의

prefix(접두사-낱말 앞에 붙어서 그 뜻을 더해주는 역할을 하는 외톨이 낱말. 

예를 들어 '첫사랑', '첫걸음'에서 '첫'은 접두사이다.)가 되는 경우가 있는지 판별하는 프로그램을 작성하고자 한다.


예를 들어 다음과 같은 숫자가 주어진다고 하자. 
 
  911
  9765999
  91125426


이 경우 911이 91125426의 prefix가 되는 경우이다. 

 

위와 같은 경우 우리는 NO라고 판별하고 위와 같은 경우가 발생하지 않는 경우 YES로 판별한다.




입력은 여러 개의 테스트 케이스로 이뤄지며 입력의 첫 번째 줄에는 테스트 케이스의 개수 T(1≤T≤40)이 입력된다.
각 테스트 케이스의 첫 번째 줄에는 숫자의 개수 N(1≤N≤10,000)이 입력되며, 
그 다음 줄부터 N개의 줄에는 판별해야 하는 N개의 숫자가 입력된다. 
숫자의 길이는 최대 100자이며, 앞에 0이 붙는 경우도 존재한다.



각 테스트 케이스에 대해 임의의 숫자가 다른 숫자의 prefix가 되는 경우가 없을 경우 "YES"를, 
그렇지 않을 경우 "NO"를 한 줄에 하나씩 테스트 케이스의 순서대로 출력한다.


2 
3 
911 
97625999 
91125426 
5 
113 
12340 
123440 
12345 
98346
NO
YES


[문자열 길이를 구하는 함수]

int strlen(char*s, int len=0){
    while(s[len]) ++len;
    return len;
}


[문자열 비교함수]
1. 문자열 s가 문자열 t보다 사전편집상 앞선다면 음수를 반환한다.
2. 두 문자열의 같다면 0을 반환한다.
3. 문자열 t가 문자열 s보다 사전편집상 앞선다면 양수를 반환한다.

int strncmp(char*s, char*t, int n){
    while(n>1 && *s==*t) ++s, ++t, --n;
    return *s - *t;
}



int strcmp(char*s, char*t){
    while(*s && *s==*t) ++s, ++t;
    return *s - *t;
}





해시, 문자열, 정렬

HancomEducation E-mail : hancomc@hotmail.com, comkiwer@naver.com Tel : 031-388-0999 FAX : 031-388-0996 정올소개 이용약관 개인정보처리방침
경기도 안양시 동안구 호계동 1065-10 협성골드프라자 601호, 경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호
Copyright@2010-2015 jungol. All right reserved.