Sherlock and Anagrams javascript로 풀기

/*

    아나그램 알고리즘의 핵심은 어찌보면 단순하다.

    문자열에서 나올 수 있는 모든 문자열의 경우의 수

    abba의 경우

    1글자로

    a

    b

    b

    a

 

    2글자로

    ab

    bb

    ba

 

    3글자로

    abb

    bba

 

    이를 구하기 위해 다중반복문을 쓸 수 있다.

    반복내용은 아래와 같다.

    0

    01

    012

    1

    12

    123

    2

    23

    3

    for(var i=0;i<strArr.length;i++){   //문자열 총 길이

        for(var j=i;j<strArr.length;j++){   //탐색할 문자열 갯수

            var str = "";

            for(var k=i;k<=j;k++){      //문자열을 순회하며 탐색할 문자열의 갯수만큼 반복

                str+=strArr[k]

            }

            console.log(str);

        }

    }

    이렇게 하면 원하는 경우의 수를 모두 뽑을 수 있다.

    (처음에 나는 조합 알고리즘을 사용해서 모든 경우의 수를 뽑아내야 하는 줄 알고 개삽질을 했다 근 1년동안..)

 

    문제를 다시 읽어보니 그냥 3중포문 돌려서 모든 경우의 수를 뽑아내고

    뽑아낸 경우의 수를 dictionary 형태로 집어넣는다.

    (이때 객체의 순서에 따라 다를 수 있으므로 모든 알파벳[a-z]을 객체에 전부 넣은 뒤에 0으로 초기화하면 순서가 고정된다.)

 

    중복된 값이 있는 경우 아나그램에 해당하므로, 1을 증가시켜준다.

 

    그 다음 해당 객체를 문자열로 변환하여 결과값에 추가해주면 된다.

 

    결과값 배열에서 2 이상이면 아나그램에 해당하며

    예를들어 kkkk 배열에서 k는 4개이고, 서로 아나그램인 경우의 수는 총 6개이다.

    이는 

    

    1 = 0

    2 = 1

    3 = 3

    4 = 6

    5 = 10

 

    즉 삼각수이다.

    (단, 삼각수가 되려면 각 결과값을 -1 해줘야 함)

    지금까지 구한 결과값을 모두 삼각수로 변환하여 합을 구하면 된다.

 

    삼각수의 공식은 i*(i+1)/2 이므로 이를 배열을 순회하며 처리해주면 된다.

 

    ㄹㅇ 겁나게 어려운 문제였지만 어찌저찌 해결함

*/

strArr="ifailuhkqq"

resArr={};

answer = [];

for(var i=0;i<strArr.length;i++){   //문자열 총 길이

    for(var j=i;j<strArr.length;j++){   //탐색할 문자열 갯수

        var str = {};

        var te = "";

        for(var k=97;k<123;k++){

            str[String.fromCharCode(k)] = 0;

        }

        for(var k=i;k<=j;k++){      //문자열을 순회하며 탐색할 문자열의 갯수만큼 반복

            str[strArr[k]]+=1

            te +=strArr[k];

        }

        console.log(te);

        str = JSON.stringify(str)

        if(!resArr[str])

            resArr[str] = 1;

        else{

            resArr[str] += 1;

            // console.log(str);

        }

    }

}

var sum = 0

for( [i,j] of Object.entries(resArr)){

    j-=1;

    sum+=j*(j+1)/2

}

return sum;

// var arr = "54321";

// var cnt = 0;

// var str =""

// var resArr = [];

// function anagrams (n,r,str) {

//     // console.log(n,r,cnt)

//     if(r == 0){

//         // str = n==r ? str+"0"+arr[n]+"1"+arr[n-1] : str+"-"+arr[n-1]

//         console.log(n,r,str)

//         resArr.push(str)

//         return str;

//     }else if(n==r){

//         for(var i=n;i>0;i--){

//             str+="+"+arr[i-1]

//         }

//         console.log(n,r,str)

//         resArr.push(str)

 

//         return str;

//     }    

//     else {

//         return anagrams(n-1,r-1,str+"*"+arr[n-1]) + anagrams(n-1,r,str);

//     }

        

// }

// var resArr = [];

// // for(var i=1;i<3;i++){

// //     str="";

// //     resArr.push(anagrams(arr.length, i,str));

// // }

//     resArr.push(anagrams(5, 3,str));