백준16925-문자열 추측
2022.03.05
문제
접근 방법
길이가 1인 경우부터 N-1 이하인 경우까지 모든 접두사와 접미사가 주어진다. 따라서 N-1 길의이 문자열 + 하나의 문자 을 조합해서 N 길이의 문자열을 만들 수 있다. 그리고 만들어진 N 길이의 문자열 중 원래 문자열 S를 찾으면 된다.
같은 길이의 문자열은 접미사, 접두사인 경우로 2개씩 존재한다. 그리고 접미사인지 접두사인지 모르기 때문에 앞뒤의 경우를 따져야 한다. 따라서 총 8개의 경우만 비교해보면 된다. 예를들어 N-1 길이의 A, B 접미사와 접두사가 있고 길이 1의 a, b 접미사와 접두사가 있을 때, A + a, a + A, A + b, b + A, B + a, a + B, B + b, b + B 총 8개의 조합이 존재한다.
이제 각 조합으로 만들어진 문자열 temp가 유효한지 확인하기만 하면 된다.
- temp 문자열이 입력으로 받은 접두사, 접미사를 포함하는지 체크한다.
- 만약 접두사와 접미사가 같은 경우라면, 각각을 단어를 포함해야 하기 때문에 temp 문자열에 해당 접미사 2개 포함되어 있어야 한다. 이를 확인하기 위해서 indexOf, lastIndexOf 를 사용했다. 두 메서드로 나온 인덱스값이 같다면 같은 위치의 단어를 가리키는 것이고, 해당 접미사, 접두사의 단어가 하나만 포함되었다는 것이다. 따라서 이러한 경우 예외를 처리해야 한다.
이제 마지막으로 부분 문자열이 접미사인지 접두사인지 확인하여 출력하면 된다.
- 원래 문자열 S에서 indexOf 메서드를 이용해서 시작 위치를 구한다. 접두사라면 가장 앞의 단어를 포함해야 하기 때문에 0이 나올 것이다.
- 하지만 고려해야할 것이 하나 있다. 원래 문자열 abab에서 접미사 ab와 접두사 ab가 같은 경우, indexOf 메서드를 호출하면 0번 인덱스를 반환하고 접미사와 접두사를 구분할 수 없다. 따라서 set을 사용해서 접두사로 사용했던 단어라는 것을 체크해야한다. 그리고 2번째로 나온 ab는 set에 포함되어 있기 때문에 접두사로 사용할 수 없고, 접미사로 사용하게 된다.
소스 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
public class Main {
static int N;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
String[] origin = new String[2 * N - 2];
List<String>[] partOfOrigin = new List[N + 1];
for (int i = 1; i <= N; i++) {
partOfOrigin[i] = new ArrayList<>();
}
for (int i = 0; i < 2 * N - 2; i++) {
String str = br.readLine();
int len = str.length();
origin[i] = str;
partOfOrigin[len].add(str);
}
String answerWord = N == 2 ? origin[0] + origin[1] : findOriginString(partOfOrigin);
System.out.println(answerWord);
System.out.println(N == 2 ? "PS" : checkSuffixOfPrefix(origin, answerWord));
}
private static String findOriginString(List<String>[] partOfOrigin) {
for (String lastPartWord : partOfOrigin[N - 1]) {
for (String firstPartWord : partOfOrigin[1]) {
String answerWordA = lastPartWord + firstPartWord;
String answerWordB = firstPartWord + lastPartWord;
if (isValidAnswer(answerWordA, partOfOrigin)) {
return answerWordA;
}
if (isValidAnswer(answerWordB, partOfOrigin)) {
return answerWordB;
}
}
}
return "";
}
private static boolean isValidAnswer(String answerWord, List<String>[] partWords) {
for (int i = 1; i < N; i++) {
String wordA = partWords[i].get(0);
String wordB = partWords[i].get(1);
if (!answerWord.contains(wordA) || !answerWord.contains(wordB)) {
return false;
}
if (wordA.equals(wordB)) {
if (answerWord.indexOf(wordA) == answerWord.lastIndexOf(wordA)) {
return false;
}
}
}
return true;
}
private static String checkSuffixOfPrefix(String[] checkStrings, String targetString) {
StringBuilder answer = new StringBuilder();
Set<String> set = new HashSet<>();
for (String checkString : checkStrings) {
if (targetString.indexOf(checkString) == 0) {
if (!set.contains(checkString)) {
set.add(checkString);
answer.append("P");
} else {
answer.append("S");
}
} else {
answer.append("S");
}
}
return answer.toString();
}
}