14Jan2020 TIL

오늘 한 일 : 

• toy problem 12 _ powerSet()
• 글자열 글자 중복 제거

---

PowerSet()을 Javascript 로 구현하기

 

Powerset는 매개변수로 주어지는 string 또는 array의 요소를 조합하여, 모든 가능한 경우의 수 만큼의 글자 조합을 도출하는 역할을 한다. 나는 과제로 string 을 매개변수로 제공받았기 때문에, string 을 기본으로 하여 해당 함수를 구현했다. 언제나 그렇듯 나는 어렵고 복잡하게 해당 함수를 구현했는데, 사람들은 간단하게 해당 함수를 구현해낸다. 

 

문제를 한 번 풀어보고 나선, 더 나은 알고리즘이 없을까? 하며, 다른 사람들의 코드를 보곤 하는데, 엄청난 고수의 느낌이 나는 간단하고 이해하기 쉬운 코드를 발견했다. 이머시브 코스가 끝날 즈음에 이 문제를 다시 푼다면, 나는 과연 이렇게 풀 수 있을까? 조금 걱정이 된다!

---

나의 방법 : 

우선, test code를 통해 sortSet이라는 함수를 발견했고, 해당 함수에 글자열 내 글자 중복을 제거하는 기능을 추가했다. 함수를 시작하기 전에, sortSet을 통해 글자 중복을 제거하고, 정렬을 시킨다. 그 후 arr에 글자 하나하나를 쪼개 담는다. 리턴할 result함수에 "" 빈문자를 담고, arr를 concat 해준다. 

 

그 후, arr와 copy 가 각각 순회하며, 조건에 맞게 조합한 글자를 result 에 담는다. (조건 : 중복 X, 글자 바뀐 중복 X). result 배열에 str이 담길 때까지 power 재귀 함수를 반복 실행시킨다.

var powerSet = function(str) {
  var sortSet = function(set) {
    var arr = set.split("");
    arr = arr.filter((el, i) => arr.indexOf(el) === i);
    return arr.sort().join("");
  };
//-> string 내의 글자 중복을 제거하고, 오름차순으로 정렬하는 글자를 리턴.

  str = sortSet(str);
  let arr = Array.from(str);
  let result = [""].concat(arr);
// -> 아래 power 함수가 str이 2글자 이하일 때,적용이 안되서 한 번 가공하고 시작한다.

  function power(arr, copy) {
    arr.map(el => {		
    //map을 쓴건.. 두번 loop돌렸더니 runJS가 작동을 안해서
      for (let element of copy) {
        if (el !== element && !el.includes(element)) {
          let string = sortSet(el + element);
          !result.includes(string) && result.push(string);
        }
      }
    });
    return result.includes(str) ? result : power(result, copy);
    //result에 str이 있을 때까지 해당 함수를 돌린다.
  }

  power(result, arr);
  return result;
};

---

다른 사람의 방법 : 

function powerset(str) {
  var resultArray = [""];
  
  function addToResult(prefix, str) {
    if(str.length === 0){return [""];}
    
    for (var i = 0; i < str.length; i++) {
      resultArray.push(prefix + str[i]);
      addToResult(prefix + str[i], str.slice(i + 1));
    }
  }
  
  addToResult('', str);
  return resultArray;
}

 

prefix 는 글자를 하나씩 늘려가고, str은 글자 수를 하나하나씩 줄여가면서, 계속 실행하다가 -> str이 빈글자가 되면 해당 함수는 끝이 나는 간단하지만, 고수의 느낌이 나는 함수다. 언제나 간단하고, 모르는 사람이 봐도 이해하기 쉽게 작성하는게 최고다. 고수니까 사진이 크게 나온 사진도 지우지 않고 남겨두기로 한다. 

 

 

출처 : https://repl.it/@kjh311/PowerSet-Recursion-Function

PowerSet Recursion Function

---

How to remove duplicates from given string _JavaScript

: 글자열 내에서 중복된 글자를 지우는 방법에 대해서

 

오늘 powerSet()을 구현하면서 글자열 내에서 중복된 글자를 간단하게 지우는 방법이 필요했다. 지우는 여러 방법 중에 내 기억에 남는 방법 2가지만 블로깅하려고 한다. 하나는 array를 이용한 방법이고, 하나는 object 를 이용한 방법이다. 막상 글자열 내에서 중복된 글자를 지우고자 할땐, 첫번째 방법을 주로 사용할 것 같다. 

 

1. arr.indexOf()를 사용하는 방법

let str = 'abccdee';
let arr = str.split('')
arr = arr.filter((el, i) => arr.indexOf(el) === i);
//['a','b','c','d','e']

arr.indexOf(value) 메소드의 특징은, array 내에서 value 가 처음으로 나오는 index만 리턴한다는 점이다. 해당 특징을 이용하여, 중복되는 배열의 요소들은 필터를 통해 걸러준다.

 

2. Object의 key 를 사용하는 방법

let str = 'abccdee'
let obj = {};
for(let i = 0; i < str.length; i++) {
  obj[str[i]] = true;
}
Object.keys(obj); // ['a','b','c','d','e'];

object 의 key 값은 중복되지 않는 다는 점에 착안한 방법인 것 같다. 근데 기억이 안나서 잘 안쓸 것 같은 방법이다.