[바미] 서로 다른 부분 문자열의 개수

문제

https://www.acmicpc.net/problem/11478

 

코드

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim();

const uniqueSubstrings = new Set();

// 입력받은 문자열에서 가능한 모든 부분 문자열을 추출
for (let start = 0; start < input.length; start++) {
    for (let end = start + 1; end <= input.length; end++) {
        const substring = input.substring(start, end);
        uniqueSubstrings.add(substring);
    }
}

// 고유한 부분 문자열의 개수 출력
console.log(uniqueSubstrings.size);

문제해설

문자열 S의 모든 서로 다른 부분 문자열의 개수를 찾는 문제입니다. Set을 사용하면 쉽게 풀 수 있는 문제죠.

 

입력 문자열 S에 대해 가능한 모든 부분 문자열을 생성하기 위해 두 개의 중첩된 반복문을 사용하여 각 반복에서 substring(start, end) 함수를 호출하여 시작 인덱스 start와 종료 인덱스 end 사이의 부분 문자열을 추출 후 추출된 부분 문자열은 Set에 추가해주는 형태입니다.

 

시간 복잡도

시간 복잡도는 알고리즘이 입력의 크기에 따라 얼마나 빠르게 실행되는지를 나타냅니다.

 

이 문제에서는 부분 문자열을 생성 할 때, 부분 문자열 처리 후 Set에 저장 할 때를 계산해야 합니다.

먼저 부분 문자열을 생성할 때를 살펴보죠. 문자열의 길이를 n이라 할 때, 모든 가능한 부분 문자열을 생성하기 위해 두 개의 중첩된 for 루프를 사용합니다.

첫 번째 루프(start)는 문자열의 시작 인덱스를 결정하고, 두 번째 루프(end)는 시작 인덱스 이후의 종료 인덱스를 결정합니다.
각 start에 대해 n - start개의 부분 문자열을 생성하기 때문에 부분 문자열의 총 개수는 1+2+3+...+n = n(n+1)/2이 되고

O(n^2)가 됩니다.

 

그 다음 부분 문자열 처리 하는 부분을 살펴볼까요? 

각 부분 문자열을 substring 메소드로 추출할 때, 평균 길이는 n/2이고, 최대 길이는 n이 됩니다.

substring 함수는 추출하는 부분 문자열의 길이에 비례하는 시간이 걸리는 특성이 있습니다.

 

그렇기 때문에 부분 문자열을 Set에 추가하는 데는 평균적으로 O(1) 시간이 걸리지만, 각 부분 문자열을 생성하고 저장하는 데 걸리는 총 시간은 각 문자열의 길이를 고려할 때 O(n^3)까지 걸릴 수 있게 됩니다.

 

그러므로 총 시간 복잡도는 최악의 경우인 O(n^3)의 시간복잡도를 가지게 됩니다.

공간 복잡도

공간 복잡도는 알고리즘이 얼마나 많은 메모리 공간을 사용하는지 나타냅니다.

 

부분 문자열을 저장할 때 Set을 사용하게 되는데 최악의 경우 모든 부분 문자열이 고유할 때, 부분 문자열의 수는 n(n+1)/2로 계산되어 O(n^2)의 공간 복잡도를 가지게 됩니다.

 

n은 입력크기를 의미하고, 여기서 n이 크게 증가할 경우 시간 복잡도가 매우 빠르게 증가하기 때문에 n의 크기에 주의해서 사용하시면 되겠습니다.