문제 설명
문자열 S가 주어졌을 때, S의 서로 다른 부분 문자열의 개수를 구하는 프로그램을 작성하시오.
부분 문자열은 S에서 연속된 일부분을 말하며, 길이가 1보다 크거나 같아야 한다.
예를 들어, ababc의 부분 문자열은 a, b, a, b, c, ab, ba, ab, bc, aba, bab, abc, abab, babc, ababc가 있고, 서로 다른것의 개수는 12개이다.
입력
첫째 줄에 문자열 S가 주어진다. S는 알파벳 소문자로만 이루어져 있고, 길이는 1,000 이하이다.
출력
첫째 줄에 S의 서로 다른 부분 문자열의 개수를 출력한다.
내 답
연속되는 모든 부분 문자열을 반복문 2개를 통해 추출하고,
중복 제거의 경우 Set을 이용해 중복을 제거했다.
시간 복잡도를 줄이고자 StringBuilder를 사용해 문자열을 담았으나,
결과적으로 950ms의 아쉬운 실행속도가 나왔다.
원인은 중복 제거 시 Set 자료구조를 사용할 때 중복을 제거하는 과정의 시간복잡도가
O(N^2)이기 때문에 시간이 오래 걸린 것으로 추측된다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.Set;
public class S3_서로다른부분문자열의개수 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String str = br.readLine();
Set<String> set = new HashSet<>();;
int len = str.length();
for (int i=0; i<len; i++) {
StringBuilder sb = new StringBuilder();
for (int j=i; j<len; j++) {
sb.append(str.charAt(j));
set.add(sb.toString());
}
}
System.out.println(set.size());
}
}
보완점
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
String input = reader.readLine();
int n = input.length();
// 접미사 배열 생성
String[] suffix = new String[n];
for (int i = 0; i < n; i++) {
suffix[i] = input.substring(i);
}
// 접미사 배열 정렬
Arrays.sort(suffix);
int len = 0;
// LCP 계산
for (int i = 1; i < n; i++) {
int curr = 0;
int minLen = Math.min(suffix[i].length(), suffix[i - 1].length());
while (curr < minLen && suffix[i].charAt(curr) == suffix[i - 1].charAt(curr)) {
curr++;
}
len += curr;
}
// 총 부분 문자열 개수에서 중복된 부분을 뺀 개수 출력
int total = (n * (n + 1)) / 2; // 총 부분 문자열 개수
System.out.println(total - len);
}
}
접미사 배열을 생성하여 정렬한 뒤,
정렬된 접미사들을 앞 뒤 접미사와 비교하며 공통 접두사 길이를 계산해 중복 부분 문자열을 제거하는 방식인
LCP 알고리즘 풀이를 사용했다.
처음 보는 알고리즘 방식이라 참신하고 좋은 방법이라는 생각이 든다.
익혀놓아야 겠다.
LCP 배열 계산
1. 가능한 모든 접미사를 저장해둔다.
apple => apple, pple, ple, le, e
2. 접미사들을 사전 순으로 정렬한다.
apple, e, le, ple, pple
3. 각 접미사들을 순회하며 이전 접미사와 비교해 공통 접두사의 길이를 계산한 LCP 배열에 저장해둔다.
apple : e => 0
e : le => 0
le : ple => 0
ple : pple => 1
따라서 중복되는 경우는 총 1가지이다!