200418 TIL 알고리즘 스터디 - hash

Apr 18, 2020 » 1.5막, TIL (Today I Learned), 스터디, 알고리즘

알고리즘 스터디 - hash

387. First Unique Character in a String

1차

var firstUniqChar = function(s) {
    const arr = s.split('');
    let obj = {};
    arr.forEach(letter => {
        obj[letter] > -1 ? obj[letter]++ : obj[letter] = 0;
    });
    let result = -1;
    for (let letter in obj) {
        if (obj[letter] === 0) {
            if (result !== -1 && arr.indexOf(letter) < result) result = arr.indexOf(letter)
            else if (result === -1) result = arr.indexOf(letter)
        }
    }
    return result
};

2차 (좀 더 직관적으로)

var firstUniqChar = function(s) {
    let obj = {};
    for (let i = 0; i < s.length; i++) {
        const letter = s[i];
        if (letter in obj) {
            obj[letter] = -1;
        } else {
            obj[letter] = i;
        }
    }
    for (let i = 0; i < s.length; i++) {
        const letter = s[i];
        if (obj[letter] > -1) return i
    }
    return -1;
};

알게된 것: object에서 key값이 number면 number 오름차순으로 아니면 넣은 순으로 출력됨

771. Jewels and Stones

var numJewelsInStones = function(J, S) {
    let result = 0;
    for (let i = 0; i < J.length; i++) {
        const jewel = J[i];
        for (let j = 0; j < S.length; j++) {
            if (S[j] === jewel) result++;
        }
    }
    return result;
};

hash인데 짧게 풀어보려고 이렇게 했음. 근데 시간복잡도 O(N제곱)이라 hash로 풀었어야함~

참고 (승훈님)

var numJewelsInStones = function(J, S) {
  h = {}
  count = 0;
  for (let c of J) {
      h[c] = 1;
  }
  for (let c of S) {
      if (c in h){
          count++;
      }
  }
  return count;
};

1002. Find Common Characters

var commonChars = function(A) {
    let obj = {};
    for (word of A) {
        let wordObj = {};
        for (let letter of word) {
            if (letter in wordObj) {
                wordObj[`${letter}-${wordObj[letter]}`] = 1
                wordObj[letter]++
            }
            else
                wordObj[letter] = 1
        }
        for (let letter in wordObj) obj[letter] ? obj[letter]++ : obj[letter] = 1;
    }
    let result = [];
    for (let letter in obj) {
        if (obj[letter] >= A.length) {
            const onlyLetter = letter.split('-')[0];
            result.push(onlyLetter);
        }
    }
    return result
};

나는 전체 값을 저장해 놓고 비교하는 방식으로 했고, 아래는 memoization 같은 방법으로 푼 풀이 (승훈님것!)

var commonChars = function(A) {
    if (A.length === 0) {
        return [];
    }
    var h = {};
    for (var c of A[0]) {
        if (c in h) {
            h[c]++;
        } else {
            h[c] = 1;
        }
    }
    for (var s of A) {
        var h2 = {}
        for (var c of s) {
            if (c in h2) {
                h2[c]++;
            } else {
                h2[c] = 1;
            }
        }
        for (var k in h) {
            if (k in h2) {
                h[k] = Math.min(h[k], h2[k]);
            } else {
                h[k] = 0;
            }
        }
    }
    var output = [];
    for (var k in h) {
        for (var i = 0; i < h[k]; i++) {
            output.push(k);
        }
    }
    return output;
};