2021.8.8 TIL 학급회장, 아나그램 (해쉬, 투포인터, 슬라이더)

학급 회장 (해쉬)

A, B, C, D, E 후보 중에서 가장 많이 뽑힌 후보는 누구인가?

 

function solution(str) {
  let answer;
  // code here;
  return answer;
}
let str = "BACBACCACCBDEDE";
console.log(solution(str)); // C

 

 

답) object 를 이용

• object 의 keys 배열 구하기 => Object.keys(obj)
• object 의 values 배열 구하기 => Object.values(obj)
• object의 특정 value값을 갖는 key를 구하기 => Object.keys(obj).find(key => obj[key] === value)

 

function solution(str) {
  let answer, obj = {};

  for(let s of str) {
    obj[s] === undefined ? obj[s] = 1 : obj[s]++;
  };

  const values = Object.values(obj);
  const max = Math.max(...values);
  answer = Object.keys(obj).find(key => obj[key] === max);

  return answer;
}

 

 

답2) new Map()을 이용한다.

• Map은 object 성격의 Set()과 비슷하다.
• for... of 반복문을 쓸 수 있다.

 

function solution(str) {
  let answer, max = 0;
  let myMap = new Map();

  for(let s of str) {
    myMap.set(s, (myMap.get(s) || 0) + 1);
  };

  for(const [key, val] of myMap) {
    if(max < val) {
      max = val;
      answer = key
    }
  };

  return answer;
}

 

 

아나그램 (해쉬)

같은 길이의 문자열 두 개가 주어졌을 때, 사용된 대/소문자가 같은지 체크

 

function solution(str1, str2) {
  let answer;
  // code here;
  return answer;
};

let a="AbaAeCe";
let b="baeeACA";
console.log(solution(a, b)); //false

 

 

답) 두 문자를 모두 Map()으로 전환하여 비교

 

function solution(str1, str2) {
  let answer = true;
  let map1 = new Map();
  let map2 = new Map();

  for(const a of str1) {
    map1.set(a, (map1.get(a) || 0) + 1);
  }
  for(const b of str2) {
    map2.set(b, (map2.get(b) || 0) + 1);
  }

  for(const [key, val] of map1) {
    if(val !== map.get(key)) {
      answer = false;
      break;
    }
  }

  return answer;
};

 

 

답2) 위의 답과 유사하지만, 한 개의 문자열을 map()에 담고, 다음 문자열을 돌아가며 갯수를 빼거나 있는지 여부를 체크하는 방법

 

function solution(str1, str2) {
  let answer = true;
  let map = new Map();

  for(const a of str1) {
    map.set(a, (map.get(a) || 0) + 1)
  };

  for(const el of str2) {
    if(!map.has(el) || map.get(el) === 0) {
      return false;
    }
    map.set(el, map.get(el) - 1);
  };

  return answer;
}

 

 

모든 아나그램 찾기

크기가 서로 다른 문자열이 주어졌을 때, 작은 문자열의 아나그램이 되는 큰 문자열 안의 부분 문자열의 갯수는 몇 개 인가? 첫 번째 매개 변수는 두 번째 매개 변수의 길이보다 크거나 같다.

 

function solution(str1, str2) {
  let answer;
  // code here;
  return answer
}
let a = "bacaAacba";
let b = "abc";
console.log(solution(a, b)); // 3 bca, acb, cba

 

 

답)

• 큰 문자열을 하나씩 돌아가며, 작은 문자열 갯수대로 자른다.
• 자른 문자열을 Map()에 담고, 작은 문자열의 Map과 같은지 비교한다.
• 단점 : 시간 복잡도 O(n^2);

 

function solution(str1, str2) {
  let answer = 0;
  let len = str2.length;

  const makeMap = (str) => {
    let map = new Map();
    for(let el of str) {
      map.set(el, (map.get(el) || 0) + 1)
    };
    return map;
  }

  const compareMap = (mapA, mapB) => {
    if(mapA.size !== mapB.size) return false;
    for(const [key, val] of mapA) {
      if(mapB.get(key) !== val) {
        return false; 
      }
    };
    return true;
  }

  const map2 = makeMap(str2);

  for(let i = 0; i < str1.length - len + 1; i++) {
    let cutStr = str1;
    cutStr = cutStr.slice(i, i + len); // slice는 mutable
    const map = makeMap(cutStr);
    compareMap(map2, map) ? answer ++ : answer;
  }

  return answer
}

 

 

답 2) 시간 복잡도 O(n)

• b a c a A a c b a
  • b a를 체크하고 거기에서 출발
• b a c a A a c b a
  • c를 체크
• b a c a A a c b a
  • a를 체크, b를 제거
• ...반복...
• b a c a A a c b a
  • a를 체크, a를 제거

 

function solution(s, t){
    let answer=0;
    let len=t.length-1;
    let sH = new Map();

    for(let x of t){
        sH.set(x, (sH.get(x) || 0)-1);
    }

      // console.log(sH); Map { 'a' => -1, 'b' => -1, 'c' => -1 }

    for(let i=0; i<len; i++){
        sH.set(s[i], (sH.get(s[i]) || 0)+1);
        if(sH.get(s[i])===0) sH.delete(s[i]);
    }

    // console.log(sH) ; Map { 'c' => -1 }

    let lt=0;

    for(let rt=len; rt<s.length; rt++){
      // (굵고 밑줄 친 글자 체크)
        sH.set(s[rt], (sH.get(s[rt]) || 0)+1);
        if(sH.get(s[rt])===0) sH.delete(s[rt]);

      // len 개의 문자가 t와 문자 구성이 같은지 체크
        if(sH.size===0) answer++;

      // (밑줄 친 글자 제거)
          sH.set(s[lt], (sH.get(s[lt]) || 0)-1);
        if(sH.get(s[lt])===0) sH.delete(s[lt]);
        lt++;
    }

    return answer;
}