백준(BOJ) 16925번 문자열 추측
문제 :
https://www.acmicpc.net/problem/16925
16925번: 문자열 추측
첫째 줄에 문자열 S의 길이 N(2 ≤ N ≤ 100)이 주어진다. 다음 2N-2개의 줄에 걸쳐서 문자열 S의 접두사와 접미사가 한 줄에 하나씩 주어진다. 모든 접두사와 접미사가 주어지기 때문에, 길이가 i(1 �
www.acmicpc.net
풀이 :
좀 더 나은 간단한 풀이가 있겠지만 일단 처음 떠올랐던 그대로 풀이를 작성하겠다.
예제 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++ )
