[알고리즘] 메타 용어_표준 용어 파싱

문제 & 문제 해석

• 문제는 간단하다. 해당 원본 문자열이 주어지고, 그 문자열을 쪼갠 배열이 있다.
• 그 배열의 모든 조합으로 원본 문자열로 만들어 각 배열의 요소 사이사이에 ('_')를 넣어주면 된다.
• 단, 정렬할 때 언더바를 기준으로 가장 첫 언더바 앞에 있는 배열의 요소가 긴 순서대로 정렬한다. 만약 첫 언더바 앞에 있는 요소의 길이가 같을 경우 그 다음 언더바로 비교한다.
• 말로 딱 읽었을 때 무슨 말인지 긴가민가 할 수 있는데 간단하게 설명하자면 아래와 같이 설명할 수 있다.

var str = "모든것을다넘겨둔채떠나려한단다";

var metaData = ["모든것을다넘겨둔채떠나려한단다", "모든" , "것을", "넘겨둔채", "다", "모든것을", "한단다", "떠나려", "넘겨둔", "채", "떠나려한단다"];

/* 위의 배열을 가지고 모든 조합으로 
	"모든것을다넘겨둔채떠나려한단다"을 만들면 된다.
	즉, 
  모든것을다넘겨둔채떠나려한단다
  모든것을_다_넘겨둔채_떠나려한단다
  모든것을_다_넘겨둔채_떠나려_한단다
  모든것을_다_넘겨둔_채_떠나려한단다
  모든것을_다_넘겨둔_채_떠나려_한단다
  모든_것을_다_넘겨둔채_떠나려한단다
  모든_것을_다_넘겨둔채_떠나려_한단다
  모든_것을_다_넘겨둔_채_떠나려한단다
  모든_것을_다_넘겨둔_채_떠나려_한단다
    을 출력하면 된다.
*/

코드

var str = "모든것을다넘겨둔채떠나려한단다";

var array = ["모든것을다넘겨둔채떠나려한단다", "모든" , "것을", "넘겨둔채", "다", "모든것을", "한단다", "떠나려", "넘겨둔", "채", "떠나려한단다"];

var array = []; //결과 값을 저장하는 배열

fn_select();

function fn_select() {

    //처음 시작했을 때는 문자열의 인덱스를 0부터 시작하고, 현재 문자열이 빈 값이므로 ""을 넣어준다.
    combienation(0, "");


    array.sort(function (a, b) {
        // 앞 부분의 길이로 비교합니다.
        const lengthA = a.indexOf("_") === -1 ? a.length : a.indexOf("_");
        const lengthB = b.indexOf("_") === -1 ? b.length : b.indexOf("_");
      
        // 길이가 긴 순서대로 정렬합니다.
        if (lengthA > lengthB) return -1;
        if (lengthA < lengthB) return 1;
        return (a.match(/_/g) || []).length < (b.match(/_/g) || []).length ? -1 : 1; //만약 같을 경우 언더스코어 기준으로 정렬한다.
    });
    
    array.forEach((o) => {
        console.log(o)
    })
}

//파라미터 : (1) 문자열 탐색 시작인덱스값, (2) 현재 진행된 문자열 
function combienation(index, currentStr) {
    if (index === str.length) { 
        //현재 원본 문자열과 시작인덱스 값이 같을 경우는 "채무재조정외부진행상태코드"라는 문자열을 만들었다는 이야기이다.
        //처음에 currentStr.replace(/\_/g, ''); 로 해서 "_"를 ''로 바꿔서 바꾼 문자열의 길이만큼 비교했는데 
        //이 경우, 해당 문자열을 누적더하기할 변수가 추가로 필요해져서 시작인덱스(index)값으로 비교해도 같다는 것을 알고 바꿨다.
        array.push(currentStr);
        return;
    }

    for (const word of metaData) { //배열에 있는 모든 요소를 반복
        /*
            word : 문자열의 시작 지점에서 탐색할 문자열
            index : searchString을 탐색할 위치. 기본값은 0

            쉽게 말하면, word는 metaData를 반복하면서 도는 건데 해당 word값이 str의 시작인덱스로 부터 시작하는 단어가 있다면 자르고,
            newStr이라는 변수에 임시 저장하고 해당 문자열의 길이만큼 시작인덱스 + 추가된 문자열 길이하고, 새로운 문자열의 추가한 currentStr을 파라미터를 다시 보내서
            재귀한다.(combienation)
        */
        if (str.startsWith(word, index)) { //원본 문자열의 해당 index가 단어 word로 시작할 경우 if문 안으로 들어온다. 
            // 만약 현재 문자열의 길이가 0이라는 것은 첫 시작 word값이므로 그대로 word를 넣으면 되고 
            // 그게 아니라 기존 문자열이 있는 경우는 currentStr(기존 문자열) + "_" + 현재 반복문을 돌고 있는 word를 추가한다.
            const newStr = currentStr.length === 0 ? word : currentStr + "_" + word; 
            combienation(index + word.length, newStr); //해당 조합함수를 다시 돈다.(재귀)
        }
    }
}

• 코드 설명은 주석으로 작성해 두었다.
• startsWith이라는 메소드를 처음봐서 꽤 많이 헤맸던 문제인데, 여기서 startsWith의 수행 과정을 보니까 아래와 같았다.
  

  1. currentStr :  index : 0 count : 0
  work1.js:33
  2. currentStr :  index : 0 count : 0
  work1.js:40
  3. currentStr :  index : 0 count : 1
  work1.js:47
  4. newStr : 모든것을다넘겨둔채떠나려한단다 index : 0 count : 1
  work1.js:51
  1. currentStr : 모든것을다넘겨둔채떠나려한단다 index : 15 count : 1
  work1.js:33
  3. currentStr :  index : 0 count : 2
  work1.js:47
  4. newStr : 모든 index : 0 count : 2
  work1.js:51
  1. currentStr : 모든 index : 2 count : 2
  work1.js:33
  2. currentStr : 모든 index : 2 count : 2
  work1.js:40
  3. currentStr : 모든 index : 2 count : 3
  work1.js:47
  4. newStr : 모든_것을 index : 2 count : 3
  work1.js:51
  1. currentStr : 모든_것을 index : 4 count : 3
  work1.js:33
  2. currentStr : 모든_것을 index : 4 count : 3
  work1.js:40
  3. currentStr : 모든_것을 index : 4 count : 4
  work1.js:47
  4. newStr : 모든_것을_다 index : 4 count : 4
  work1.js:51
  1. currentStr : 모든_것을_다 index : 5 count : 4
  work1.js:33
  2. currentStr : 모든_것을_다 index : 5 count : 4
  work1.js:40
  3. currentStr : 모든_것을_다 index : 5 count : 5
  work1.js:47
  4. newStr : 모든_것을_다_넘겨둔채 index : 5 count : 5
  work1.js:51
  1. currentStr : 모든_것을_다_넘겨둔채 index : 9 count : 5
  work1.js:33
  2. currentStr : 모든_것을_다_넘겨둔채 index : 9 count : 5
  work1.js:40
  3. currentStr : 모든_것을_다_넘겨둔채 index : 9 count : 6
  work1.js:47
  4. newStr : 모든_것을_다_넘겨둔채_떠나려 index : 9 count : 6
  work1.js:51
  1. currentStr : 모든_것을_다_넘겨둔채_떠나려 index : 12 count : 6
  work1.js:33
  2. currentStr : 모든_것을_다_넘겨둔채_떠나려 index : 12 count : 6
  work1.js:40
  3. currentStr : 모든_것을_다_넘겨둔채_떠나려 index : 12 count : 7
  work1.js:47
  4. newStr : 모든_것을_다_넘겨둔채_떠나려_한단다 index : 12 count : 7
  work1.js:51
  1. currentStr : 모든_것을_다_넘겨둔채_떠나려_한단다 index : 15 count : 7
  work1.js:33
  3. currentStr : 모든_것을_다_넘겨둔채 index : 9 count : 8
  work1.js:47
  4. newStr : 모든_것을_다_넘겨둔채_떠나려한단다 index : 9 count : 8
  work1.js:51
  1. currentStr : 모든_것을_다_넘겨둔채_떠나려한단다 index : 15 count : 8
  work1.js:33
  3. currentStr : 모든_것을_다 index : 5 count : 9
  work1.js:47
  4. newStr : 모든_것을_다_넘겨둔 index : 5 count : 9
  work1.js:51
  1. currentStr : 모든_것을_다_넘겨둔 index : 8 count : 9
  work1.js:33
  2. currentStr : 모든_것을_다_넘겨둔 index : 8 count : 9
  work1.js:40
  3. currentStr : 모든_것을_다_넘겨둔 index : 8 count : 10
  work1.js:47
  4. newStr : 모든_것을_다_넘겨둔_채 index : 8 count : 10
  work1.js:51
  1. currentStr : 모든_것을_다_넘겨둔_채 index : 9 count : 10
  work1.js:33
  2. currentStr : 모든_것을_다_넘겨둔_채 index : 9 count : 10
  work1.js:40
  3. currentStr : 모든_것을_다_넘겨둔_채 index : 9 count : 11
  work1.js:47
  4. newStr : 모든_것을_다_넘겨둔_채_떠나려 index : 9 count : 11
  work1.js:51

• 위의 사진을 보면 이제 더이상 반복할 게 없으면, 전에 해당 인덱스부터 시작하는 단어가 있었을 때의 인덱스로 돌아가 다시 재귀를 한다는 것을 알 수 있었다.
• 기본값이 0이라는 것을 더이상 탐색할 것이 없었을 때 0이된다는 것을 볼 수 있다.(콘솔에 찍은 데이터를 보면)

결과

느낀 점

• startswith메소드가 다한 느낌...
• 처음에는 문자열을 뒤부터 쪼개가면서 시작하는 인덱스로부터 해당 배열에 시작하는 문자가 있다면 시작인덱스를 늘려주고(찾은 문자의 길이만큼 +), 못찾으면 뒤에서 다시 하나 자르는 방식으로 했다가 도저히 안되가지고 꽤 애를 많이 먹었던 문제이다.
• 근데, 고민과 무색하게 이미 알아서 처리해주는 메소드가 있었다...