티스토리 뷰

문제 풀이

[BOJ 8892] 팰린드롬

RiKang 2018. 1. 9. 08:58

 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=02*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=02*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
[BOJ 8892] 팰린드롬  (0) 2018.01.09
함수 문제 풀이  (0) 2018.01.04
문자열 관련 함수 문제 풀이  (0) 2018.01.03
문자열 문제 풀이  (0) 2017.12.05