#11478 서로 다른 부분 문자열의 개수

문제

문자열 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의 서로 다른 부분 문자열의 개수를 출력한다.

예제 입력 1 복사

ababc

예제 출력 1 복사

12

 

설명

모든 문자열 조합의 경우의 수를 구하고 중복을 제거하면 쉽게 답을 낼 수 있습니다.

 

코드

 

fs 모듈을 사용하여 입력값을 읽어들인 후 split() 을 사용하여 문자열을 분리합니다.

이후 이중 반복문과 slice(), join() 함수를 사용하여 문자열의 모든 조합 경우의 수를 구하고 미리 선언해둔 arr 배열에 push() 합니다.

 

 

중복되는 값을 제거하기 위해 Set 객체를 선언하여 arr 배열을 인자로 전달하고 size 메소드를 사용하여 중복을 제거한 경우의 수를 구하면 됩니다.

 

결과

 

주의할 점

 처음에는 Set 객체를 먼저 선언하고 이중 반복문 안에서 add 메소드를 사용하여 모든 경우의 수를 바로바로 Set객체에 할당해주었습니다. size 메소드를 사용하여 답을 출력했을 때 예제 출력과 같아서 백준에 코드를 제출했으나 시간 초과라는 답변을 받았습니다.

Array의 push와 Set의 add가 성능 면에서 차이가 존재하는 것 같아서 찾아보았는데 이에 대한 답을 StackOverflow에서 찾을 수 있었습니다.

1. 요소 추가 : Array의 push 메소드가 Set의 add 메소드보다 약 4배 정도 빠릅니다.
2. 요소 갱신 or 반복 : 요소의 개수가 적은 경우 push 메소드가 2배 빠르고, 요소의 개수가 많은 경우 push 메소드가 4배 빠릅니다. 즉, 요소의 개수가 증가할수록 속도 차이가 기하급수적으로 늘어나는 것을 알 수 있습니다.
3. 요소 삭제 : 요소의 개수가 적은 경우 add 메소드가 push 메소드보다 3배 빠르고, 많은 경우 add 메소드가 약 23배 빠르다. (출처 https://stackoverflow.com/questions/39007637/javascript-set-vs-array-performance )

Javascript Set vs. Array performance

즉, add가 push보다 느리기 때문에 시간 초과가 발생했습니다. 따라서 이를 해결하기 위해 배열에 push를 사용하여 모든 경우의 수를 할당하고, 이를 Set객체에 인자로 사용하여 시간 초과 문제를 해결하였습니다.

 

출처

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