티스토리 뷰
2012 ACM-ICPC Daejeon regional 의 기출문제입니다. 백준 8892 에서 채점할 수 있습니다.
요약 )
문제는 k개의 단어가 주어졌을 때, 그 중 2개의 단어를 붙여서 만든 문자열 중 팰린드롬이 있으면 그 중 아무거나 출력하고, 팰린드롬이 없으면 0을 출력하는 것입니다. 친절하게도 모든 단어 길이의 합이 10000이하임이 보장되므로, 만들 수 있는 모든 문자열을 만들어서 하나 하나 검사하여도 제한 시간내에 해결할 수 있습니다.
팰린드롬 체크 함수 )
모든 문자열을 검사하려면, 먼저 문자열이 팰린드롬인지를 검사하는 함수를 만들어야 합니다. 팰린드롬의 정의에 따라 아래와 같이 구현할 수 있습니다.
1 2 3 4 5 6 7 | // code by RiKang, weeklyps.com bool is_pal(string s1){ // s1이 팰린드롬인지 여부를 반환 for(int i=0; 2*i<s1.size(); i++) if(s1[i]!=s1[s1.size()-i-1]) return false; return true; } | cs |
대칭 형태가 아님이 발견되면 false 를 리턴하고, 대칭 형태가 보장되면 true를 리턴하는 식입니다.
모든 문자열 검사하기 )
이제 팰린드롬인지를 검사하는 함수를 만들었으므로, k개의 단어 중 2개씩 골라서 합친 문자열을 is_pal()로 검사해주면 끝입니다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 | // code by RiKang, weeklyps.com // 2012 ACM-ICPC Daejeon regional - E // BOJ 8892 팰린드롬 // O(k*sum) solution #include <bits/stdc++.h> using namespace::std; int k; string s[105]; bool is_pal(string s1){ // s1이 팰린드롬인지 여부를 반환 for(int i=0; 2*i<s1.size(); i++) if(s1[i]!=s1[s1.size()-i-1]) return false; return true; } void solve(){ scanf("%d",&k); for(int i=0; i<k; i++) cin>>s[i]; for(int i=0; i<k; i++){ for(int j=0; j<k; j++){ if(i==j) continue; if(is_pal(s[i]+s[j])){ cout<<s[i]+s[j]<<endl; // 팰린드롬일 경우 출력 return; // 팰린드롬을 찾았으므로 함수를 강제종료 } } } printf("0\n"); } int main(){ int t; scanf("%d",&t); while(t--){ solve(); } return 0; } | cs |
is_pal() 의 시간복잡도는 O(문자열의 길이)이며, 모든 s[i]+s[j]의 길이를 모두 합하면 2*(k-1)*(모든 단어의 길이의 합) 이기 때문에 총 시간복잡도는 O(k*(모든 단어의 길이의 합))임을 알 수 있습니다.
모든 s[i]+s[j]의 길이를 모두 합하면 2*(k-1)*(모든 단어의 길이의 합)인 이유)
특정 값 x ( 0<=x<n 인 자연수)에 대해,
s[x]이 이 문자열에 포함되는 횟수는 i=x 일 경우에 k-1 번, j=x 일 경우에 k-1번입니다.
i=x 일 경우, 즉 s[x]+s[j]꼴에선 j 가 x를 제외한, k-1개의 수가 가능하고
j=x 일 경우, 즉 s[i]+s[x]꼴에선 i가 x를 제외한, k-1개의 수가 가능하기 때문입니다.
따라서 '모든 s[i]+s[j]의 길이의 합'에서 s[x] 부분이 차지하는 길이는 2*(k-1)*|s[x]| 가 됩니다. (|s[x]| = s[x]의 길이)
그리고 2*(k-1)*|s[0]| + 2*(k-1)*|s[1]| + ... + 2*(k-1)*|s[k]| = 2*(k-1)*(모든 단어의 길이의 합) 입니다.
'문제 풀이' 카테고리의 다른 글
[BOJ 8895] 막대 배치 (0) | 2018.01.10 |
---|---|
[BOJ 8896] 가위 바위 보 (0) | 2018.01.09 |
함수 문제 풀이 (0) | 2018.01.04 |
문자열 관련 함수 문제 풀이 (0) | 2018.01.03 |
문자열 문제 풀이 (0) | 2017.12.05 |