[JS] 백준 11478번 : 서로 다른 부분 문자열의 개수

 

Question

[JS-자바스크립트] 백준 11478번 : 서로 다른 부분 문자열의 개수

문자열 S가 주어졌을 때, S의 서로 다른 부분 문자열의 개수를 구하는 프로그램을 작성하시오.

부분 문자열은 S에서 연속된 일부분을 말하며, 길이가 1보다 크거나 같아야 한다.

예를 들어, ababc의 부분 문자열은 a, b, a, b, c, ab, ba, ab, bc, aba, bab, abc, abab, babc, ababc가 있고, 서로 다른 것의 개수는 12개이다.

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

 

입력

첫째 줄에 문자열 S가 주어진다. S는 알파벳 소문자로만 이루어져 있고, 길이는 1,000 이하이다.

 

출력

첫째 줄에 S의 서로 다른 부분 문자열의 개수를 출력한다.

 

입력예시

ababc

 

출력예시

12

 

 

---

 

 

My Code

const input = require("fs").readFileSync("dev/stdin").toString().trim().split(/\s/);

const s = input[0];
let str = new Set();


for (let i = 0; i < s.length; i++) {
    for (let j = i; j < s.length; j++) {
        str.add(s.substring(i, j + 1))
    }
}


console.log(str.size);

맞았습니다!!

 

 

HOW? (풀이방법)

 

1. 빈 set 자료형을 선언한다. (set 자료형을 사용하는 이유는 중복되는 문자열을 걸러내기 위해서)
2. 문자열로 만들 수 있는 모든 경우의 수를 for 중첩 문을 통해 만들어낸다(완전 탐색)
3. 만들어진 문자열을 set 자료형에 추가한다. 중복되는 문자열은 추가되지 않는다.
4. set의 size를 출력한다.

 

 

 

 

어떻게 풀어야 하나.

확실한 거는 이것도 배열을 이용하면 안 되겠다 였다.

처음에는 map으로 만들어서 중복을 걸러야겠다 생각했다가

중복을 허용하지 않는 자료형인 set을 이용했다!

 

것보다 for 중첩 문 이용하는 건 구글링을 통해 알아냈다.

막상 풀어봐도 적용을 언제 해야 하나 이렇게 까먹는다!!!

익숙해질 때까지 보자....

 

 

 

 

 

혹시나 브루트 포스(완전탐색)과 set자료형이 뭔지 궁금하시다면 아래포스팅을 나랑 같이 확인합시다.

 

[Algorithms/Algorithms] - [알고리즘 기본] 완전 탐색 (브루트 포스 Brute Force)

[알고리즘 기본] 완전 탐색 (브루트 포스 Brute Force)

[Front-End/JavaScript] - [자바스크립트 기본] 자바스크립트 자료형 Set 개념정리

[자바스크립트 기본] 자바스크립트 자료형 Set 개념정리