boj 10096 세 친구

www.acmicpc.net/problem/10096

10096번: 세 친구

문자열 S가 2번 반복되어있는 문자열에 문자 하나를 무작위로 넣었습니다.

 

이렇게 완성된 문자열에서 문자열 S를 찾는 문제입니다.

 

일단 같은 문자열이 2번 반복되어있기때문에 주어지는 입력은 홀수개의 문자로 이루어져 있습니다. (2n+1개)

저는 이 문자열은 앞에서부터

n, n+1개로 끊은 문자열 2개

n+1, n개로 끊은 문자열 2개

이렇게 그룹을 나누었습니다.

 

나눈 문자열을 순차적으로 비교를 하였고,

다른부분이 1개면 S는 n개로 끊었던 문자열이 되고, 2개 이상이면 S를 구할 수 없는 것입니다.

 

두 개의 그룹이

모두 true면 답이 2개이므로 2개가 같으면 문자열 출력, 다르면 NOT UNIQUE

모두 false면 답이 없으므로 NOT POSSIBLE

아니면 true인 경우의 문자열을 출력해주시면 됩니다.

 

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static char ch[];
    static int N;
 
    static boolean solve(char s1[], char s2[]) {
        int cnt = 0;
        for (int i = 0, j = 0; i < s1.length; i++, j++) {
            if (s1[i] != s2[j]) {
                if (cnt > 0)
                    return false;
                cnt++;
                i--;
            }
        }
 
        return true;
    }
 
    static void func() {
        if (N % 2 == 0) {
            System.out.println("NOT POSSIBLE");
            return;
        }
        char s1[] = new char[N / 2];
        char s2[] = new char[N / 2 + 1];
        char s3[] = new char[N / 2];
        char s4[] = new char[N / 2 + 1];
 
        System.arraycopy(ch, 0, s1, 0, N / 2);
        System.arraycopy(ch, N / 2, s2, 0, N / 2 + 1);
 
        System.arraycopy(ch, 0, s4, 0, N / 2 + 1);
        System.arraycopy(ch, N / 2 + 1, s3, 0, N / 2);
 
        boolean result2 = solve(s3, s4);
        boolean result1 = solve(s1, s2);
 
        if (result1 && result2) {
            String str1 = String.valueOf(s1);
            String str2 = String.valueOf(s3);
            if (str1.contains(str2))
                System.out.println(String.valueOf(s1));
            else
                System.out.println("NOT UNIQUE");
        } else if (!result1 && !result2)
            System.out.println("NOT POSSIBLE");
        else if (result1)
            System.out.println(String.valueOf(s1));
        else
            System.out.println(String.valueOf(s3));
 
    }
 
    static void input() throws Exception {
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
 
        st = new StringTokenizer(br.readLine());
        ch = st.nextToken().toCharArray();
    }
 
    public static void main(String[] args) throws Exception {
        input();
        func();
    }
}