[백준/BOJ] 11478번 서로 다른 부분 문자열의 개수 (Javascript / Node js)

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

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

문제 해석

입력 받은 문자열에서 모든 경우의 부분집합들을 추출해낸 후, 중복된 값들만 제거해주면 되는 간단한 문제이다.

Javascript에서는 Set객체를 사용해서 중복을 제거할 수 있기 때문에 입력 받은 문자열에서 모든 경우의 부분집합들을 추출해 내는 알고리즘만 구현해 내면 된다.

 

나는 2중 for문을 사용해서 첫번째 for문의 i 값으로 잘라낼 문자열의 길이를 정의했고, 두번째 for문의 j 값으로 잘라낼 문자열의 시작부분을 정의했다. 그러니 자연스럽게 잘라낼 문자열의 마지막 인덱스는 j(시작 인덱스) + i(잘라낼 길이) 가 되고 이를 이용해 slice함수가 사용 가능해진다.

 

for(let i=1; i<=input.length; i++){
    for(let j=0; j<input.length-i+1; j++){
        set.add(input.slice(j,j+i));
    }
}

 

그리고 잘라낸 문자열들을 중복제거가 자동으로 되는 Set객체에 넣어주고 for문이 다 돌고 난 후에 Set객체의 크기를 출력해주면 "서로 다른 부분 문자열의 개수"가 출력된다.

 

전체코드

const fs = require("fs");

const input = fs.readFileSync("../input.txt").toString().trim();

let set = new Set([]);

for(let i=1; i<=input.length; i++){
    for(let j=0; j<input.length-i+1; j++){
        set.add(input.slice(j,j+i));
    }
}

console.log(set.size);