배열로 구현이 안될 때는 객체, Map 자료형을 고려

개요

 

최근 코테준비를 다시 시작하면서 1단계를 비롯한 낮은 난이도 문제들을 해결하며 뿌듯해하고 있었다.

 

하지만, 정답률이 낮은 문제로 갈 수록 내가 아는 지식, 방식내에서 해결 안되는 문제들이 많았고 DFS, 탐욕법, 동적계획법 같은 개념들을 모르고 진행하는데에 한계를 느꼈다.

 

보통 해결되지 않는 상황은 크게 두 가지로 나누어지는데 

 

1. 해당 문제를 풀기위한 작전, 방식 자체가 안떠올라 시작 자체를 못하는 경우

 

2. 어느정도 구현은 했으나 테스트 혹은 제출 단계에서 일부 테스트 케이스를 통과하지 못하는 경우

 

이 두 가지가 단순히 많이 풀어보기 보단 위에서 말한 익숙치 않은 알고리즘, 자료구조에 대한 이해도가 낮다 생각해 코테 문제를 풀며 접하는 여러 상황에 대해서 기록하고자 했다.

 

 

문제

 

프로그래머스 뉴스 클러스터링 문제

https://school.programmers.co.kr/learn/courses/30/lessons/17677

프로그래머스

 

 

두 개의 단어(a,b)가 주어지고 각 단어를 두 글자 씩 끊어 생성된 단어들을 비교하며 a,b에서 생성된 단어들 간의 교집합과 합집합을 구하는 문제이다.

 

 

처음 내가 접근한 방법으로는 각 단어들을 두 글자씩 끊어 배열에 넣어 두 배열을 includes로 비교하면서 교집합을 구하고, 총 단어 수의 합에서 교집합을 빼 합집합으로 구했다.

 

오류

내가 생각치 못한 부분중, 검증 기준이 되는 배열에 일치하면서 동일한 단어가 더 많은 경우엔 문제가 되지 않으나, 반대로 적은 경우 교집합의 개수가 잘못 측정되었다.

 

또한 배열의 경우 중복요소들에 대하여 단순 개별 저장되기에 배열의 길이가 늘어나는 경우 연산의 수도 수 없이 늘어나게 된다.

 

문제 해결을 위해 각 단어에 해당하는 빈도수를 기록하고 각 단어 간 같은 단어가 있는 경우 더 적은 빈도수를 택해 교집합의 수로 더하고 합집합의 경우 더 많은 수를 더하면 되기에 key-value로 이루어진 구조가 필요했다.

 

 

Map

 

단순 index를 통한 순서와 값들로 구성된 array 배열과는 다르게 Map의 경우 키-값 쌍으로 이루어져있다.

 

또한 객체와는 다르게 Key의 경우 다양한 자료형을 허용한다는 차이가 있으며 Map에서 제공하는 메서드를 통해 값을 더하거나 빼곤한다.

 

//  새로운 Map 객체를 생성
const map1 = new Map();

// 생성된 Map에 새로운 값을 삽입
map1.set("a", 1);
map1.set("b", 2);
map1.set("c", 3);


// 값을 읽는방법 get
console.log(map1.get("a"));
// Expected output: 1 


// 배열 객체의 length에 해당하는 map 객체의 크기를 반환
console.log(map1.size);
// Expected output: 3


// Map의 키가 중복값이 있는 경우 나중값이 적용됨
let map1 = new Map([
    ['a',1],
    ['a',2],
    ['b',3]
]) // {"a" => 2, "b" => 3}

 

⚠️ 주의

객체와는 유사하나 값을 설정할 때 객체처럼 map[key]와 같이 사용한다면 일반 객체로 취급되어 여러 제약이 발생한다

 

따라서, 전용 메서드인 set, get을 사용해 Map의 값들에 대하여 접근해야한다.

 

응용

 

객체와의 차이 중 하나로 Map 자료형은 for..of 혹은 forEach 같은 순회가 가능하다. 물론, 객체도 가능하지만 객체의 경우 Object.keys를 거쳐야하기에 더 간단한 로직으로 순회할 수 있다.

 

myMap.forEach((value, key) => {
  console.log(`${key} = ${value}`);
});


for (const [key, value] of myMap) {
  console.log(`${key} = ${value}`);
}


for (const key of myMap.keys()) {
  console.log(key);
}


for (const value of myMap.values()) {
  console.log(value);
}

 

일반 배열 순회와는 다르게 value와 key를 접근해 내부 로직을 구현할 수 있다.

 

 

문제 해결

 

function solution(str1, str2) {
    str1 = str1.toLowerCase();
    str2 = str2.toLowerCase();
    
    const getMultiset = (str) => {
        const arr = [];
        for (let i = 0; i < str.length - 1; i++) {
            const pair = str.substr(i, 2);
            if (/^[a-z]{2}$/.test(pair)) arr.push(pair);
        }
        return arr;
    };
    
    const arr1 = getMultiset(str1);
    const arr2 = getMultiset(str2);
    
    // 빈도수 맵 생성
    const createFrequencyMap = (arr) => {
      const map = new Map();
      arr.forEach(item => {
        map.set(item, (map.get(item) || 0) + 1);
      });
      return map;
    };
    
    const map1 = createFrequencyMap(arr1);
    const map2 = createFrequencyMap(arr2);

 

먼저 각 문자열들만을 짝으로 맞추어 배열에 저장했다(arr1, arr2) 정규식을 통해 문자열인 경우에만 짝으로 분류하고, 배열을  순회하며 key에 해당하는 value를 1씩 증가시켜주어 map을 생성했다.

 

    let intersection = 0;
    let union = 0;
    const allKeys = new Set([...map1.keys(), ...map2.keys()]);

    allKeys.forEach(key => {
        const count1 = map1.get(key) || 0;
        const count2 = map2.get(key) || 0;
        intersection += Math.min(count1, count2);
        union += Math.max(count1, count2);
    });

    const similarity = union === 0 ? 1 : intersection / union;
    return Math.floor(similarity * 65536);

 

이 부분부터는 내가 했던 방법이 너무 길어 gpt의 도움으로 가독성 좋게 수정했다

 

각 맵의 전체 존재하는 key로만 이루어진 set를 만들고, 해당 key로 각 map을 순회하며 다음과정을 거친다.

 

1. key에 해당하는 value가 한 개만 존재하는 경우, Math.min을 통해 교집합은 0으로 채택

2. key에 해당하는 value가 모두 존재하는 경우, Math.min을 통해 더 적은 개수를 교집합 수로 채택

3. key에 해당하는 value중 큰 수(Math.max)를 합집합의 수로 채택해 더함

 

합집합이 0인경우 즉 모두 공집합인 경우 조건에 나온대로 1을 반환

 

참고 및 마무리

 

적다보니 객체로 해도 충분히 풀렸을 거 같은데 힌트에서 Map을 보게되어 배우는김에 해당 방법으로 접근하게 되었다.

 

key도 문자열이고 입력되는 순서도 es6 이상부터는 상관없다니 다음부터 특수한 경우가 아니라면 객체가 더 가독성이 좋을 수도 있겠다고 생각했다.

 

https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Map

Map - JavaScript | MDN

 

https://inpa.tistory.com/entry/JS-%F0%9F%93%9A-%EC%9E%90%EB%A3%8C%ED%98%95-Map-%F0%9F%9A%A9-%EC%A0%95%EB%A6%AC

[JS] 📚 자바스크립트 자료형 Map 🚩 정리