[ 07.22 ] 멱집합(2)

이제 멱집합의 개념은 알겠음. 하지만 식으로 작성하는것이 여전히 어려웠다.
그래서 그냥 템플릿을 외워버리기로 했다. 끝.

👻 문제1.

한가지 밥에 n개의 반찬이 있을때, 밥과 함께 먹을 수 있는 반찬의 모든 경우의 수를 배열에 담아 리턴하세요.

👻 주의사항

반찬은 영문으로 작성이 되어 있습니다.
반찬은 중복되지 않습니다.
반찬을 먹지 않는 것도 포함됩니다. (출력되는 2차원 배열은 빈 배열을 포함합니다.)
반찬은 3개 이상 99개 이하입니다.
출력되는 배열은 전부 사전식 순서(lexical order)로 정렬되어야 합니다.

👻 입출력 예시

let output = missHouseMeal(["eggroll", "kimchi", "fishSoup"]);
console.log(output);
/*
[ [], 
  [ 'eggroll' ], 
  [ 'eggroll', 'fishSoup' ], 
  [ 'eggroll', 'fishSoup', 'kimchi' ], 
  [ 'eggroll', 'kimchi' ], 
  [ 'fishSoup' ], 
  [ 'fishSoup', 'kimchi' ], 
  [ 'kimchi' ]
] 
*/

☠️ 문제 이해하기

입출력예시에 나온것처럼 주어진 배열안의 반찬들을 먹을수 있는 모든 경우의 수를 구해야 한다 단, 한가지메뉴가 여러번 겹치지 않도록 먹어야 하며, ([eggroll,eggroll,eggroll] -> 이런식으로 먹을 수 없음.)
반찬을 전혀 먹지않은 경우도 포함시켜야 한다. ([])

☠️ 수도코드

1. 출력되는 배열은 전부 사전식 순서로 나열되야 하므로 반찬배열들을 sorting 처리 한 후 시작해준다.
2. 이중배열로 최종출력 해야하므로 빈배열 result 에 변수하나 지정
3. 솔팅된 반찬배열만큼 계속적으로 반복해서 반찬들이 담겨야 하므로 재귀함수가 필요하다.
4. 임의의 배열에 반찬을 하나씩 담고 count++
5. 종료조건은 count 가 반찬배열의 길이에 도달했을때 최종출력할 result 에 임의의 배열을 push 해준다.
6. result 도 한번 더 솔팅하여 리턴해준다.

function missHouseMeal(banchan) {
  // TODO: 여기에 코드를 작성합니다.
  let result = [];
  let sorting = banchan.sort();

  const recursive = (count = 0 ,banchanArr=[]) => {
    if(idx === banchan.length){
      result.push(banchanArr)
      return
    }
    recursive(count+1,banchanArr)
    recursive(count+1,banchanArr.concat(banchan[count]))
    
  }
  recursive()
  return result.sort();
}

👻 문제2.

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

👻 주의사항

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

☠️ 문제 이해하기

앞의 문제와 상당히 비슷하다. 아니, 거의 똑같다고 볼 수 있다.
단지 배열이냐 string 이냐, 그 차이뿐.
그리고 이 문제에서는 output2 예시를 보면 문자열에 중복되는 문자가 있으나 최종 출력본에는 중복되는 문자는 하나만 나오는 것을 볼 수 있다.
기존 풀었던 문제에 중복되는 문자열에 대한 함수만 추가하면 될것 같다.

☠️ 수도코드

1. 알파벳을 순차적으로 sorting 하기 위해서 배열형태로 바꿔준 수 sorting 해준다.
2. 중복되는 문자열을 빼주기 위해서 sorting 한 배열의 요소들과 비교하여 똑같은 값이 있으면 첫번째 값만 리턴, 아니라면 첫번째 값에 그다음값들을 추가해주는 함수를 작성해준다. -> reduce
3. 중복을 제거해주는 함수의 length 만큼 반복해서 재귀적으로 탐색하는 함수를 짠다.
4. 재귀조건은 임시의 빈배열에 값을 넣고, 그 빈배열에 요소들을 하나씩 넣어준다. 그리고 count++ 해준다.
5. sorting된 배열의 길이만큼 count 가 도달하면 임시배열에 둔 것을 result.push 하여 넣어주며 종료한다.
6. 최종적으로 result 를 sorting 하고 리턴한다.

const powerSet = function (str) {
  // TODO: 여기에 코드를 작성합니다.
  let sorting = str.split('').sort();
  // ["j", "j", "m", "p", "u"]
  let result = [];
  let dupe = sorting.reduce((a,c)=>{
    if(a[a.length-1] === c){
      return a;
    }else{
      return a.concat(c)
    }
  });

  const recursive = (n = 0, strs = '') => {
    if(n === dupe.length){
      result.push(strs);
      return;
    }
    recursive(n+1,strs);
    recursive(n+1,strs.concat(dupe[n]))
  }
  recursive();
  return result.sort();

};