Prm 11 : powerSet

powerSet

문제

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

입력

인자 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']

 

---

 

풀이

 

 

배운점

1. str을 쪼개서 배열로 만드는 것은 split을 해도 되고, spread parameter를 사용해도 된다.

 

2. 중복 제거는 deduplicated로 명칭하면 된다.

정렬 후 reduce를 이용해서 acc에 item을 하나씩 붙여나가는데, 정렬은 같은 문자끼리 모아서 중복을 제거하기 위함이다.

>>알파벳 순서대로 정렬하기 위해서 굳이 sort 안에 파라미터 a, b 를 집어넣을 필요가 없다.

만약에 acc의 끝( acc[acc.length - 1] ) 요소가 붙여야할 item과 같다면 그냥 acc를 return 함으로써 item을 acc에 붙이지 않고,

item과 다르다면 acc.concat을 통해 item을 붙인 값을 acc로 넣어주는 방식으로 중복제거를 한다.

 

3. 재귀

아래 사진과 같이 트리구조로 재귀를 실행한다.

재귀를 실행하면서 index를 하나씩 늘리고, 알파벳 요소를 하나씩 포함시켜 나감으로써 부분집합을 구한다.

종료점은 index가 배열의 길이만큼 됬을 때이고, 이때 만들어진 문자열 subset을 결과 문자열 Subsets에 push 하도록 한다.

2^n의 시간복잡도가 필요한 문제이다.