[코테] 멱집합(Power set)

 

문제

하나의 집합을 의미하는 문자열을 입력받아 각 문자를 가지고 만들 수 있는 모든 부분집합을 리턴해야 합니다.

 

입력

인자 1: str

• string 타입의 공백이 없는 알파벳 소문자 문자열

출력

• 배열(arr)을 리턴해야 합니다.
• arr[i]는 각 부분집합의 원소로 구성된 문자열

주의사항

• arr[i]는 각 부분집합을 구성하는 원소를 연결한 문자열입니다.
• arr[i]는 알파벳 순서로 정렬되어야 합니다.
• 집합은 중복된 원소를 허용하지 않습니다.
• 부분집합은 빈 문자열을 포함합니다.
• arr은 사전식 순서(lexical order)로 정렬되어야 합니다.

입출력 예시

let output1 = powerSet('abc');
console.log(output1); // ['', 'a', 'ab', 'abc', 'ac', 'b', 'bc', 'c']

let output2 = powerSet('jjump');
console.log(output2); // ['', 'j', 'jm', 'jmp', 'jmpu', 'jmu', 'jp', 'jpu', 'ju', 'm', 'mp', 'mpu', 'mu', 'p', 'pu', 'u']

 

 

문제 이해

멱집합은 집합의 모든 부분집합을 원소로하는 집합이라는 뜻입니다. 말로 하면 어려울 수 있는데 간단한 예시를 보면금방 직관적으로 이해하실 것입니다.

 

집합 B: { 1, 2 }

B의 멱집합:  { ∅, {1}, {2}, {1,2} }

 

그럼 {1,2,3}의 멱집합은 뭘까요?

{ ∅, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3} } 입니다.

규칙성을 찾기 위해 마지막 원소인 3이 들어간 것과 들어가지 않은 것으로 분류해 보겠습니다.

3이 들어가지 않은 것	{ ∅, {1}, {2}, {1,2} }
3이 들어간 것	{ {3}, {1,3}, {2,3}, {1,2,3} }

 

규칙을 찾아보면 3이 들어가지 않은 것에 이전 { 1, 2 }의 멱집합이 들어 있고,

3이 들어간 것에는 { 1, 2 }의 멱집합의 각 원소에 3을 넣은 것과 같은 것을 알 수 있습니다.

 

경우의 수로 따져보면 집합의 각 원소마다 부분집합에 '포함하는 것' 과 '포함하지 않는 것' 이라는 2가지 선택지가 있기 때문에 2배씩 늘어나고, 집합에 원소가 하나씩 늘어날 때마다( 원소 3 )늘어난 원소가 들어간 부분집합들( {3}, {1,3}, {2,3}, {1,2,3} )만 추가하는 규칙이 있습니다.

 

풀이 💡

자바스크립트 코드로 나타내면 다음과 같습니다.✏✒🖋🖊🖍🖌

const powerSet = function (str) {
  let arr = [...new Set(str)].sort();
  if (arr.length === 1) return ["", ...arr];
  let last = arr.pop();
  let lastArr = powerSet(arr).map((x) => x + last);
  return powerSet(arr).concat(lastArr).sort();
};

 

중복이 제거된 결과값을 원하기 때문에 Set클래스에 넣었다가 빼서 중복을 제거합니다.

 

let arr = [...new Set(str)].sort();

 

재귀함수(Recursive Method)로 구현할 것이기 때문에 탈출 부분인 base case를 작성합니다.

반복될 수록 마지막 원소를 제거해가며 재귀적으로 호출될 것이기 때문에 arr의 길이가 1이 되면 ""과 마지막 원소를 포함한 배열을 리턴합니다.

 

// Base Case
if (arr.length === 1) return ["", ...arr];  // '1' -> ['', '1']

 

마지막 원소를 제거한 배열을 재귀함수로 리턴합니다.

( powerSet(arr) : 처음과 같이 문자열이 아닌 배열을 넣어도 Set 클래스에 의해 Set타입이 되므로 상관없습니다.)

이때, 마지막 원소가 들어간 부분집합을 map메서드로 만들어서 concat메서드로 합친뒤 정렬하여 리턴합니다.

let last = arr.pop();		// arr=['1', '2'] , last = '3'
let lastArr = powerSet(arr).map((x) => x + last);  // lastArr = ['3', '13', '23', '123']
return powerSet(arr).concat(lastArr).sort();    // powerSet(arr) = ['', '1', '2', '12']
// ['', '1', '2', '12', '3', '13', '23', '123'] 가 되고 sort()를 해주면 원하는 값이 출력된다.

 

 

멱집합은 중고등학교 때에도 배우고 넘어가지만 프로그래밍으로 구현하기엔 생각해내기 쉽지 않은 문제입니다.

더 좋은 풀이법이나 궁금한 점이 있으시면 댓글 부탁드립니다. 감사합니다.