백준(BOJ) 16925번 문자열 추측

문제 :

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

16925번: 문자열 추측

 

풀이 :

 

좀 더 나은 간단한 풀이가 있겠지만 일단 처음 떠올랐던 그대로 풀이를 작성하겠다.

 

예제 1번 ) 5 ba a abab a aba baba ab aba 으로 설명해보자면

 

우선 크기로 정렬 시 a a ab ba aba aba abab baba 가 나오게 된다.

                                   (1)(2)                               (3)     (4)

 

이때 정답이 되는 문자는  (1) + (3) , (1) + (4) , (2) + (3), (2) + (4) 후보들 중 하나가 될 것이다.

 

따라서 네 가지 경우중 답이 된다면 바로 출력 후 종료해주자.

 

후보들을 골랐다면 indexes를 통해 속해있는 문자열에 시작 인덱스들을 모두 찾아주는(Find) 배열을 만든다.

 

2 * n -2 동안 prefix 거나 ( string.find 했을 시 0이 나오는 경우 )

 

suffix 거나 ( 0이 아니라면 indexes를 통해 나온 가장 나중 인덱스 + 현재 cur의 합이 n이 됐을 때 suffix이다)

 

cand = ababa에 cur = ba에 대한 suffix 예)

ba는 Find시 두 번 속하고 1과 3이 나오게 된다. 이때 가장 나중에 나온 숫자인 3 그리고 ba의 크기 2

를 더할 시 ababa에 사이즈가 나오므로 suffix이다.

 

 

모두 prefix 거나 suffix가 나온다면 P인지 S인지 적어주자. 이미 P가 나왔다면

 

그다음은 S이므로 set을 통해 처리해주었다.

 

 

코드 ( C++ )