SW Expert Academy
SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!
swexpertacademy.com
단어의 부분집합들의 사전순이다.
일단 부분집합 단어를 사전순으로 배열하는 법을 생각해보자.
답은????
1. 단어의 접미어를 다 따오자.
2. 접미어 따온 단어들을 정렬하자.
3. 정렬한 단어들에 대한 접두어 단어를 나열한다. (접두어 단어 나열하면서 중복으로 오는건 지우면 된다.)
그러면 이것은 사전순으로 가져오게 된것이다.
그래서 코드를 작성했다.
|
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
|
import java.util.*;
import java.io.*;
import java.math.*;
public class D210329_SWEA1257 {
static int n;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int a = Integer.parseInt(br.readLine());
for(int z = 1 ; z <= a ; z++) {
int n = Integer.parseInt(br.readLine()); // n번째. 없으면 none 출력
String str = br.readLine();
String[] strs = new String[str.length()];
//접미어 배열
for(int i = 0 ; i < strs.length; i++)
strs[i] = str.substring(i);
/*
for(int i=0; i<strs.length; i++) {
System.out.println(strs[i]);
}
*/
//정렬
Arrays.sort(strs);
//접두어 배열
ArrayList<String> list = new ArrayList<String>();
for(int i = 0 ; i < strs.length ; i++) {
String tmp = strs[i];
for(int j = 0 ; j < tmp.length(); j++) {
String tmp2 = tmp.substring(0, j+1);
if(!list.contains(tmp2))
list.add(tmp2);
}
}
for(int i = 0 ; i < list.size(); i++)
System.out.println(list.get(i));
/*
if(list.size() < n)
System.out.println("#"+z+ " none");
else
System.out.println("#" + z + " " +list.get(n-1));
*/
}
}
}
|
cs |
결과는 어땟을까??
그렇다. 3번째 과정에 대한 코드를 작성하려니깐 N^3의 시간이 걸려서 폭발해버리고 만것이다.
(37번째줄의 list.contains도 하나의 for문급으로 시간이 걸린다. 아마 순차적으로 찾을꺼니깐....)
이것을 어떻게 해결해야 할까???
여기서 알아야 하는것은????
LCP행렬이라는 것을 만들어야 한다.. LCP란 최대 공통 접두어의 갯수이다.
그러니깐
위에서 2번에서 접미어 따온 단어들을 정렬한 후에 그것에 대한 최대 공통 접두어의 개수를 만들어야 한다.
이것을 보자.
a 와 ana의 최대 공통 접두어는 1개이다. 실제로 1개가 접두어가 나열되면서 포함이 되지 않았다.
ana와 anana의 최대공통접두어는 3개이다. 실제로 3개의 접두어가 나열되면서 포함이 되지 않았다.
그러면 이것에 대한 LCP 행렬은 어떻게 되나???
이렇게 표현이 될것이다.
그러면 이것을 어떻게 써먹냐???
여기가 머리가 터진다.
각 단어가 몇번째부터 몇번째까지인지 어떻게 표현할지 생각해보자.
일단 직관적으로 생각하면
a 의 접두어 배열은 1번째이다.
ana의 접두어 배열은 2~3번째이다.
anana의 접두어 배열은 4~5번째이다.
banana의 접두어 배열은 6~11번째이다.
na의 접두어 배열은 12~13번째이다.
nana의 접두어 배열은 14~15번째이다.
이것을 수식으로 나타내보자.
a의 접두어 배열은 단어의 길이인 1번 번째이다.
ana의 접두어 배열은 2 ~ (a의 마지막번째(1) + 단어길이(3) - lcp(1)) 3번째이다.
anana의 접두어 배열은 4 ~ (ana의 마지막번째(3) + 단어길이(5) - lcp(3)) 5번쨰이다.
banana의 접두어 배열은 6 ~ (anana의 마지막번째(5) + 단어길이(6) - lcp(0)) 11번쨰이다.
na의 접두어 배열은 12~(banana의 마지막번째(11) + 단어길이(2) - lcp(0))13번째이다.
nana의 접두어 배열은 14~(na의 마지막번째(13) + 단어길이(4) - lcp(2))15번째이다.
이것 코드로 구현하면 된다.
물론 lcp도 코드로 구현해야 한다. 이건 그래도 할만하니...
lcp 행렬을 구하는건 37~ 51번째줄
k번째 단어를 구하는것은 63번부터 75번째줄 까지이다. 66번째줄 생각하는게 시간이 제일 오래 걸렸다.
슥 보면 알겠지만 N^2컷이다.
|
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
73
74
75
76
77
78
79
80
|
import java.util.*;
import java.io.*;
import java.math.*;
public class D210329_SWEA1257_improvment {
static int[] sa = new int[10000];
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int a = Integer.parseInt(br.readLine());
for(int z = 1 ; z <= a ; z++) {
int n = Integer.parseInt(br.readLine()); // n번째. 없으면 none 출력
String str = br.readLine();
Integer[] suffixArr = new Integer[str.length()];
for(int i = 0 ; i < suffixArr.length ; i++ ) {
suffixArr[i] = i;
}
/*
for(int i = 0 ; i < suffixArr.length ; i++) {
System.out.println(str.substring(suffixArr[i])); // 접미사 배열
}
*/
Arrays.sort(suffixArr, (aa,bb)->str.substring(aa).compareTo(str.substring(bb)));
//sufficArr[3] == str.substring(3);
String strs[] = new String[str.length()];
for(int i = 0 ; i < suffixArr.length ; i++) {
strs[i] = str.substring(suffixArr[i]);
}
Integer[] lcp = new Integer[str.length()];
lcp[0] = 0;
for(int i = 1 ; i < suffixArr.length ; i++) {
int min_compare = Math.min(strs[i-1].length(), strs[i].length());
int cnt = 0;
for(int j = 0 ; j < min_compare ; j++) {
if(strs[i-1].substring(0,j+1).equals(strs[i].substring(0,j+1)))
cnt++;
else
break;
}
lcp[i] = cnt;
}
/* lcp 구함
for(int i = 0 ; i < lcp.length ; i++)
System.out.println(lcp[i]);
*/
int ans = 0;
boolean flag = false;
//번쨰
for(int i = 0 ; i < strs.length; i++) {
int tmp = ans + strs[i].length() - lcp[i];
if(tmp >= n) { // 더한것이 목표수보다 커버리면
System.out.println("#"+z+" "+strs[i].substring(0, lcp[i]+ (n-ans)));
// 이게 제일 중요함. flag = true;
break;
}
else
ans = ans + strs[i].length() - lcp[i];
}
if(flag == false)
System.out.println("#"+z+" "+"none");
}
}
}
|
cs |
'뚝배기 터진 문제_SWEA' 카테고리의 다른 글
| [SWEA] 1244. 최대 상금 (0) | 2021.04.01 |
|---|