CF 1092 C Prefixes and Suffixes

Codeforces 1092C Prefixes and Suffixes

문제 보러 가기

https://codeforces.com/contest/1092/problem/C

문제 설명

문자열 길이 정수 n 을 입력받는다. 그리고 2*n-2 개의 문자열을 입력받는다. 이때 문자열들은 다음을 만족한다.

1 입력받는 문자열은 길이가 (1 ~ n-1)인 문자열이 각각 두개씩 있다.

2 각각 문자열들은 n 길이의 문자열 S의 접두어거나 접미어이다.

이때 각각의 문자열이 S(접미어), P(접두어)인지 2*n -2 길이로 문자열 정보를 출력하라.

예제

입력

5

ba

a

abab

a

aba

baba

ab

aba

출력

SPPSPSPS

입력

3

a

aa

aa

a

출력

PPSS

입력

2

a

c

출력

PS

문제에 대해 이야기해본다.

내가 느끼기엔, 이 문제는 Div 3 Contest의 C문제로 나오기엔 조금 어려웠다는 생각이 들기도 했다. Div2 C급이라고 느꼈다. 어쨌든, 만약 내가 문제를 출제할 기회가 있으면 이런 문제를 그대로 내고 싶기도하다. 

처음에 내가 이 문제를 접했을때 조금 긴 지문 때문에 중요한 정보인 각각의 문자열이 정확하게 (1~n-1) 의 길이의 문자열이 두개씩 있다는 것을 간과했었기 때문에, 예제 1 부터 계속 제출했을때 틀렸다. 근데 그 이유를 몰랐다. 지문을 이해했을 땐 내 정답 출력도 전혀 문제가 없었기 때문이다. 그때 내 출력이 아마 SSPSPSPP 였나 그랬을 것이다. 근데 문자열 길이 1짜리 두개가 S이므로 틀린 정답인데 어쨋든 문제풀땐 몰랐다 ㅡㅡ  그래서 뭐지 하면서 바로 D로 넘어갔는데 내수준으로서 D도 엄청 난해했으니 ...

문제 푼 사람 수가 A 5000 ~ , B 5000~, C 900 ~ D 100~ D2 100~ E 50~ F 300~ ..ㅠㅠ..

잡설이였고

해당문제는 우선 온전한 문자열을 추론하여, 경우의수 두개를 먼저 고려하여 시작한다.

 n-1 길이의 두 문자열을 가져와서 우선적으로 온전한 string을 만드는 것이다. 

두 경우의수는 코드로 다음과 같이 표현가능하다. x + y.back() , y+ x.back() 으로 가능하다.

그래서 일단 만든 임시 스트링 "A"에 대해 각각 문자열 매칭을 시도한다.

만약 0에서부터 매칭하면 Prefix로 적절한 문자열이며, 만약 뒤에서부터 매칭하면 Suffix로 적절한 문자열이다. 단, 해당 문자열이 Prefix든 Suffix든 매칭하게되면 해당 문자열의 길이와 똑같을 다른 문자열은 자동으로 그 반대방향에 매칭하는 문자열이어야한다. 만약 이를 만족하지 않으면 임시 스트링 "A"가 틀린것이다. 그리고 자동적으로 "B"가 매칭되는것이다.

--- 

위 까지가 정확한 접근이였다.

나는 콘테스트가 끝나고 문제를 정확히 이해한뒤에 다시 접근했는데, 어떻게 접근했냐라고 쓸려고했는데 몇 줄을 써내려가다 굳이 틀린 생각을 공유할 필요는 없을 것같다.

이 문제는 콘테스트때 해결하지 못했다. 콘테스트가 끝나고 생각을 정리하고 논리적으로 소스를 짜는데 koosaga님의 소스를 많이 참조하였다.

이상.