10096번: 세 친구
준규, 해빈, 진욱이는 다음과 같은 게임을 한다. 먼저, 준규가 문자열 S를 고른다. 그 다음, 해빈이는 S의 뒤에 S를 붙인 새로운 문자열 T를 만든다. 마지막으로 진욱이는 문자열 T의 어딘가(시작이
www.acmicpc.net
문자열 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인 경우의 문자열을 출력해주시면 됩니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
|
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();
}
}
|
cs |
'algorithm > String' 카테고리의 다른 글
| boj 10453 문자열 변환 (0) | 2024.07.24 |
|---|---|
| boj 9081 단어 맞추기 (0) | 2021.12.15 |