문자열 S의 길이가 N-1이하인 모든 접두사와 접미사를 이용해, 원래 문자열 S를 만들어보려고 한다. S의 모든 접두사와 접미사가 주어졌을 때, 원래 문자열 S가 무엇인지 구하는 프로그램을 작성하시오.
제한사항
없음
입력
첫째 줄에 문자열 S의 길이 N(2 ≤ N ≤ 100)이 주어진다. 다음 2N-2개의 줄에 걸쳐서 문자열 S의 접두사와 접미사가 한 줄에 하나씩 주어진다. 모든 접두사와 접미사가 주어지기 때문에, 길이가 i(1 ≤ i ≤ N-1)인 문자열의 개수는 항상 2개이다.
출력
첫째 줄에 입력으로 주어진 접두사와 접미사를 이용해 만들 수 있는 문자열 S를 출력한다.
둘째 줄에는 입력으로 주어진 문자열이 접두사이면 'P', 접미사이면 'S'를 순서대로 출력한다.
입출력 예
input
return
5 ba a abab a aba baba ab aba
ababa SPPSPSPS
3 a aa aa a
aaa PPSS
2 a c
ac PS/
나의 문제풀이
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(bufferedReader.readLine());
// 입력값을 배열에 넣어준다.
String[] strArray = new String[N * 2 - 2];
for (int i = 0; i < 2 * N - 2; i++) {
strArray[i] = bufferedReader.readLine();
}
bufferedReader.close();
// 가장 긴 문자열을 찾아 각각 배열에 넣어준다.
String[] maxStr = new String[2];
int maxCnt = 0;
for (String s : strArray) {
if (s.length() == N - 1) {
maxStr[maxCnt++] = s;
}
}
// 가장 긴 문자열을 이용해 2개의 원본 문자열 후보를 만든다.
String[] originStr = new String[2];
originStr[0] = maxStr[0] + maxStr[1].substring(N-2);
originStr[1] = maxStr[1] + maxStr[0].substring(N-2);
// 접두사와 접미사가 같은 문자열을 대비해 접두사 사용 유무를 확인할 배열을 선언한다.
boolean[] prefix;
StringBuilder stringBuilder;
for (String origin : originStr) {
prefix = new boolean[N];
stringBuilder = new StringBuilder();
for (String str : strArray) {
// 원래 문자열에서 문자열의 길이 만큼 자른 문자열이 해당 문자열과 같으면 접두사로 표기
if (str.equals(origin.substring(0, str.length()))) {
if (!prefix[str.length()]) {
stringBuilder.append("P");
prefix[str.length()] = true;
} else {
stringBuilder.append("S");
}
// 마지막 문자 비교로 접미사인지 확인한다.
} else if (str.equals(origin.substring(origin.length() - str.length()))){
stringBuilder.append("S");
}
}
// 접두사와 접미사의 합이 입력된 문자열의 길이와 같아야한다.
if (stringBuilder.length() == strArray.length) {
System.out.println(origin);
System.out.println(stringBuilder.toString());
break;
}
}
}
}
입력값을 불러와 사용할 수 있도록 배열에 넣어준다.
문자열 배열을 반복해 가장 긴 문자열을 찾아 maxStr배열에 넣어준다.
가장 긴 문자열 2개중 어느 문자열이 접두사, 접미사인지 모르기 때문에 각각 접두사로 하고 다른 문자열의 마지막 문자를 접미사로 하여 원본 문자열 배열에 넣어준다.
원본 문자열 2개를 반복하면서 어느 문자열이 조건에 맞는지 확인한다.
접두사와 접미사가 같은 문자열을 대비해 접두사 사용 유무를 확인할 배열을 초기화한다.
문자열의 구분하고 출력값을 입력할 stringBuilder를 초기화한다.
문자열 배열을 반복한다.
해당 문자열이 원본 문자열의 시작부터 비교해 일치하면 접두사이므로 stringBuilder에 P값을 넣어주고 해당 길이의 문자열을 접두사에 사용함을 체크 한다.
접두사로 일치했지만, 이미 접두사에 들어갔으면 S값을 넣어준다.
접두사에 일치하지 않고 접미사에 일치한 경우 S값을 넣어준다.
stringBuilder에 길이가 입력된 문자열의 길이와 같은 경우, 해당 원본 문자열을 출력하고 stringBuilder를 출력한다.
문자열 문제는 알고리즘 테스트에서는 잘 나오지 않지만 문자열을 가지고 조건을 구현을 하는 부분에 있어서는 개인적으로 실무에서 생각해야 하는 부분으로 잘할 수 있어야 되지 않을까 싶다. 처음에는 긴 문자열을 사용해서 원본 문자열을 만들지 않고 짧은 문자열과 긴 문자열의 조합으로 4가지의 경우의 수를 이용해서 하나의 원본 문자열을 만들어서 사용했을 때는 89%에서 실패를 했는데, 아마 4가지 중에 중복이 되는 문자열이 있는데 접두사와 접미사의 구분이 잘 못 되는 반례가 있지 않을까 싶다. 그 이후로는 긴 문자열을 사용해서 원본 문자열 케이스를 2개로 나눠 접두사, 접미사 구분을 했는데, 구분 조건에서 접두사인지만 확인을 하고 접두사일 경우 중복 여부를 확인해 접두사와 접미사로 구분을 했는데, 오히려 84%에서 실패를 했다. 접두사와 접미사의 구분을 하는 조건에서 처음에는 문자열 케이스가 1개에서 했기 때문에 접두사가 아니면 접미사라는 게 전제로 있었지만, 문자열 케이스가 2개일 경우에는 한 가지 문자열은 원본 문자열이 아니기 때문에 애초에 접두사와 접미사로 성립이 하지 않을 수 있기 때문에 접두사와 접미사를 모두 확인해 구분을 해주도록 조건을 주어 문자열을 추측할 수 있도록 해 정답을 해결할 수 있었다. 반례들을 생각을 하고 구현을 한다고 했지만, 생각지 못한 반례가 있어 해당 조건을 잘 파악할 수 있도록 여전히 경험이 많이 필요한 듯하다.
