[BOJ 16925] 문자열 추측 (Java)

BOJ 16925 문자열 추측

문제풀이

접두사, 접미사가 나오는 문자열 문제라서 엄청 어렵지 않을까 생각했는데 단순 구현을 통해서 해결 가능한 문제였다.

1. 주어진 접두사, 접미사 중 가장 긴 것들을 a + b의 마지막 문자 그리고 b + a의 마지막 문자로 붙여서 원본 문자열을 만든다. 두 개 다 해보지 않으면 틀리는 경우가 있기 때문이다.

   한쪽으로만 붙였을 때는 다음과 같은 케이스는 통과하지 못한다.
   가장 긴 두 개만 보면 abab가 먼저 보이지만
   주어진 접두사, 접미사를 보면 baba가 맞기 때문이다.
   4
   aba
   bab
   a
   b
   ba
   ba

2. 자바의 String.indexOf(str)을 이용하여 접두사와 접미사를 구분한다. indexOf(str) 의 값이 0이면 접두사로 사용할 수 있는 것이다. 하지만 접두사와 접미사에 동시에 속할 수 있는 것이 있기 때문에 set에 접두사를 넣고 같은 것이 나왔을 때 이미 set에 존재하면 접미사로 취급한다. indexOf(str)의 값이 0이 아닌 경우에는 제일 뒷 문자가 원본 문자열의 마지막 문자와 동일한지 확인한 후 같을 경우에만 접미사로 취급한다.
3. 분류한 접두사, 접미사의 개수가 맞으면 해당 원본 문자열이 맞으며 아니면 다음 문자열로 시도한다.

구현코드

import java.util.HashSet;
import java.util.Scanner;

public class Main {
	
	static String[] origin;
	static String[] input;
	static HashSet<String> set;
	static StringBuilder sb;
	static int N;
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		N = sc.nextInt();
		
		set = new HashSet<>();
		origin = new String[2];
		input = new String[2 * N - 2];
		
		// s, p로 이름지었지만 사실 어떤 것이 접두사인지 접미사인지 모른다.
		String s = null, p = null;
		for(int i = 0 ; i < 2 * N - 2 ; ++i) {
			input[i] = sc.next();
			if(input[i].length() == N - 1) {
				// 가장 긴 접두사와 접미사를 찾는다.
				if(s == null) {
					s = input[i];
				} else p = input[i];
			}
		}
		
		// 각각 앞에 오는 경우로 원본 문자열을 만든다. 
		origin[0] = s + p.charAt(p.length() - 1);
		origin[1] = p + s.charAt(s.length() - 1);
		
		for(String ori : origin) {
			// 각 문자열에 대한 접두사이므로 set은 반드시 비워준다.
			set.clear();
			sb = new StringBuilder();
			for(String fix : input) {
				// 0이면 접두사로 사용할 수 있다. 
				if(ori.indexOf(fix) == 0) {
					// 접두사와 접미사 양쪽에 속할 수 있는 경우를 고려한다. 
					if(!set.contains(fix)) {
						set.add(fix);
						sb.append("P");
					} else sb.append("S");
				} else {
					// 마지막 문자 비교로 접미사인지 확인한다. 
					if(fix.charAt(fix.length() - 1) == ori.charAt(ori.length() - 1)) {
						sb.append("S");
					}
				}
			}
			// 빌더의 길이가 접두사, 접미사의 총 개수와 같아야한다.
			if(sb.length() == 2 * N - 2) {
				System.out.println(ori);
				System.out.println(sb.toString());
				return;
			}
		}
		System.out.println(origin[1]);
		System.out.println(sb.toString());
	}
}