[Algorithm] powerSet 알고리즘,문자열 부분 집합 문제 Javascript, Node.js

 

 

문제

 

하나의 집합으로 구성된 문자열을 입력받는다.

각각의 문자를 사용해서 만들 수 있는 모든 부분 집합을 반환하세요.

 

입력

string 타입, 공백 없는 소문자 알파벳 문자열

 

출력

배열을 반환한다. arr[i]는 문자열로 구성된 부분집합

 

주의사항

• arr[i]는 알파벳 순서로 정렬되어야 한다.
• 부분집합은 빈 문자열을 포함한다.
• 출력값 arr는 사전식으로 정렬되어야 한다.
• 중복된 요소는 제거한다.

 

 

풀이

 

가장 먼저 입력받은 문자열의 중복을 제거해준다. Javascript에서 중복된 문자열을 제거하는 방법은 reduce 사용, Set사용, filter 함수를 사용하는 방법 총 3가지가 있다. 여기서는 간단하게 Set 함수를 사용한다. Set은 배열과 다르게 중복된 요소를 허용하지 않지만 배열의 순서를 보장하지는 않는다. 따라서 sort 함수를 사용해서 문자열의 위치를 바로잡는다.

 

부분집합을 생성하는 과정은 for 반복문과 재귀 함수를 함께 사용한다. 예를 들어 'ABC' 문자열을 입력받는 경우 부분집합 생성은 1개, 2개, 3개 까지 늘어나고 다시 재귀함수를 탈출하면서 다음 반복문으로 넘어가서 한 요소를 건너뛰고 다시 1개, 2개, 3개 문자열을 구성한다.

 

 

최초 빈 문자열과 0으로 재귀 호출이 시작된다. arr 첫번째 요소를 입력받고, arr 길이 만큼 반복문이 돌게 되고 다음 요소를 하나씩 추가하면서 최종 길이까지 도달하게 된다. 만약 최종 지점까지 도달한 경우 다음 요소인 C로 넘어가서 최종 지점인 C까지 반복문이 순회하게 된다.

 

 

Javascript Code 1

 

function powerSet(str) {

    // 중복 제거
    const arr = Array.from(new Set(str)).sort();
    let result = [];

    // 재귀 함수 호출
    const recur = (newStr, start) =>{
        // 첫번째 요소 입력
        result.push(newStr);
        // 배열 길이만큼 순회(1씩 증가하면서 문자열 추가)        
        for(let i=start; i<arr.length; i++){
            recur(newStr+arr[i], i+1);
        }
    }

    // 초기값은 빈 문자열과 0번째 부터 시작함.
    recur('', 0);
    return result;
 }

 

Javascript Code 2

 

2개의 재귀함수를 호출하면서 부분집합을 찾아내는 방법이다. 입력받은 문자열의 중복을 제거할 때 reduce() 함수를 사용했다. 최초 빈문자열('')이 입력되면 바로 그대로 입력값에 추가하고, 나머지 재귀함수는 다음 index를 찾는다. A가 추가되고 첫번째 재귀함수는 그대로 출력, 두번째 재귀함수는 다음 index를 찾는다. 이 과정을 반복하면서 문자열의 부분집합을 구해낸다.

 

 

function Ref_powerSet(str) {

    // 중복 제거
    const deduplicated = str.split('').sort().reduce((acc, item) => {
        if (acc[acc.length - 1] === item) {
            return acc;
        } else {
            return acc.concat(item);
        }
    });

    let subSets = [];
    const pickOrNot = (idx, subset) => {
        // base case
        if (idx === deduplicated.length) {
            // 마지막 문자까지 검토한 경우
            subSets.push(subset);
            return;
        }

        // recursive case
        // idx번째 문자가 포함되지 않는 경우
        pickOrNot(idx + 1, subset);

        // idx번째 문자가 포함되는 경우
        pickOrNot(idx + 1, subset + deduplicated[idx]);
    };

    pickOrNot(0, '');

    return subSets.sort();
};

 

 

 

정리

 

Javascript에서 문자열 혹은 배열의 중복을 제거하는 방법은 여러가지다. 가장 심플한 방법이 ES6에서 도입된 Set 함수를 사용하는 것이다. 다만 사용상 주의사항은 중복을 허용하지 않지만 문자열의 순서도 보장되지 않기 때문에 sort() 함수와 함께 사용해야 한다.

 

모든 재귀함수는 반복문으로 표현할 수 있다. 위의 두 소스코드도 결국 두번의 반복문이 작동하는 것이고, 하나는 재귀를 두번째는 둘다 재귀함수를 사용한 것이다. 재귀함수를 사용해 문제를 풀 때는 base case와 reculsive case 두가지로 구분해서 탈출조건과 재귀조건을 명확하게 구분한다.

 

 

 

[Algorithm] 퀵 정렬(Quick Sort) Javascript, Node.js 구현하기 (백준 2751 수 정렬하기 2)

 

[Algorithm] 백준 2447번 별 찍기 - 10 Node.js Javascript