Map 과 Set 에 대하여..

알고리즘 문제를 풀다가 연습과정을 적어볼까 한다.

예전부터 궁금했던 부분인데, 알고리즘 문제를 풀이하면서 이용하게 되어 그런김에 한번 포스팅해보고자 한다. 그리구 앞으로도 좀 문제들을 풀다가 배운 내용이 있으면, 배운 정도에 한해서 블로그 포스팅을 해보는게 좋겠다 싶어서 다른 내용들도 곧 포스팅 해보겠다.

---

Map은 객체와 다른가?

알고리즘 문제를 풀다보면 시간복잡도를 신경쓰지 않을 수가 없다. 그리고 시간복잡도가 가장 민감하게 다뤄지는것은 결국 반복업무인데, 예를 들어서 배열 [1, 2, 3, 4, 5] 에서 1을 찾고 싶을 때, 가장 배열 앞에 존재하기 때문에, 하나를 찾고 바로 반복문을 나오게 된다면(break) 시간복잡도는 O(1) 이겠지만, 5를 찾는 경우 처음부터 끝까지 검색을 해야하기에, 배열의 길이 n 만큼의 시간복잡도 O(n) 이 나오게 된다.

 

n 이 무수하게 커질 수록 당연하게도 계산 시간을 늘어날 수밖에 없기에, 단순한 값이 검색과정에도 어떠한 데이터 구조를 사용하는것이 유리할지 고민을 해야한다. 놀라운 점은 n 개의 데이터를 어떠한 방법으로 구조화 하느냐에 따라(배열, 해쉬...) 시간 복잡도에 급격한 차이가 발생하기 때문이다. 생각해보면 검색에서 O(n) 이 O(1) 이 된다고 생각해보면, 그리고 이 n 이 10억이상의 숫자라고 생각해보면, 너무나 큰 차이라는 것이 느껴지게 된다.

 

Map 예기를 하다가 좀 센 느낌이 있지만, Map 역시 여러 데이터를 집합적으로 다루는 하나의 형식이며, 시간복잡도와 밀접한 관계가 있기 때문에 먼저 시간복잡도에 대해서 주저리 설명을 했다..

 

Map

맵(Map)은 키가 있는 데이터를 저장한다는 점에서 객체와 그다지 차이가 없어보이긴 한다. 차이점이라면 Map의 key 값에는 다양한 자료형을 허용한다는 점에 있다. 예시를 살펴보자

let map1 = new Map() // map을 만든다.

map1.set(1, 'num1');
map1.set('1', 'str1');
map1.set(true, 'bool1');

// 객체는 키를 문자형으로 암묵적으로 변환시킨다.
// 허나 맵은 타입을 변환시키지 않고 그대로 유지한다.

map1.get(1); // 'num1'
map1.get('1'); // 'str1'

// 맵의 크기를 측정할 수 있다.
map1.size; // 3

숫자와 문자형을 그대로 구별하여 key 에 저장하기 때문에, 좀 더 정확하게 key 값을 분류할 수 있다.

map 에는 다음과 같은 주요 메서드와 프로퍼티가 있다.

 

• new Map() : 맵을 생성
• map.set(key, value): key 를 이용해 value 를 저장.
• map.get(key) : key 에 해당하는 값을 가져온다. 없다면 undefined
• map.has(key) : key 의 존재에 대한 boolean 값을 반환한다.
• map.delete(key) : key에 해당하는 값을 삭제
• map.clear() : map 안 모든 요소를 제거한다
• map.size : map 의 요소개수를 반환.

이게 객체랑 비슷하기 때문에, 간혹 map 을 객체처럼 사용할 때가 있는데, 그렇게 하면 안된다. 이유는 객체로 접근하게 될 시 key 값을 암묵적으로 문자형으로 변환시켜버리기 때문이다. 실제 console.log 를 찍어봐도 찍히는 형태가 다름을 확인할 수 있다.

let str = ['a', 'b', 'c'];

let map1 = new Map();

str.forEach((v) => map1[v] = 1);
console.log(map1); // Map(0) {a: 1, b: 1, c: 1, size: 0}

str.forEach((v) => map1.set(v, 1));
console.log(map1); // Map(3) {'a' => 1, 'b' => 1, 'c' => 1}

일반적으로 객체처럼 활용했을 때와, 그렇지 않을 때의 콘솔 반환값에 차이가 보인다.

프로퍼티값이 형성이 되지 않는다.

key 와 value 값이 표현되어있다.

map 를 객체처럼 활용하여 key 값을 추가하였다면, map 에서 활용가능한 메서드들이 작동을 하지 않는 경우가 생긴다. 왜냐하면 위에서 처럼 프로퍼티를 찾을 수가 없기 때문이다. 

 

실제로 코딩테스트 문제를 풀이하다가, 처음에 데이터를 객체처럼 접근하여 생성하였다가, 나중에 .delete(key) 메서드를 사용하려고 하였더니 그냥 작동을 하지 않았다. 즉, 해당하는 key 값을 찾을 수가 없었기 때문이다. Map 을 제대로 활용하고 싶다면 반드시 Map의 사용법에 맞게 사용을 하자. 

 

코드로 예시를 들진 않겠지만, 또다른 예시로 맵은 객체조차 키값으로 가질 수 있다. 이러한 특징을 고려하건데, 만약 맵을 객체처럼 다룬다면 이 key 값으로 저장된 객체조차 문자열로 변경시킬 테니, 당연히 문제가 발생한다.

 

Map의 요소에 반복 작업하기

맵의 경우 세가지 메서드를 사용해 맵의 각 요소에 반복 작업을 할 수 있다. 이 부분도 일반 객체처럼 따로 이터러블한 작업을 통해 해야 되는 점과 차이점이 생겼다. 더 간편하다는 의미!

 

• map.keys() : 각 요소의 키를 모은 반복 가능한 객체를 반환.(이터러블)
• map.values() : 각 요소의 값을 모은 이터러블 객체를 반환.
• map.entries() : 요소의 [키, 값] 을 한 쌍으로 하는 이터러블 객체를 반환. for..of.. 반복문의 기초로 쓰인다.

let recipeMap = new Map([
  ['cucumber', 500],
  ['tomatoes', 350],
  ['onion',    50]
]);

// 키(vegetable)를 대상으로 순회.
for (let vegetable of recipeMap.keys()) {
  alert(vegetable); // cucumber, tomatoes, onion
}

// 값(amount)을 대상으로 순회.
for (let amount of recipeMap.values()) {
  alert(amount); // 500, 350, 50
}

// [키, 값] 쌍을 대상으로 순회.
for (let entry of recipeMap) { // recipeMap.entries()와 동일.
  alert(entry); // cucumber,500 ...
}

참고로 맵의 경우 값이 삽입된 순서조차 기억을 한다. 그래서 반복문을 돌릴 때 삽입된 순서대로 순회를 하게 된다. 이런것이 없는 개체와는 또다른 차이점이다. 알고있으면 나중에 분명 써먹을 때가 있을 것 같다..

 

간단한 예제문제를 통해 Map을 사용해보자

프로그래머스 level.0 의 문제 : A를 B로 변경하기

 

"문자열 before 와 문자열 after 가 매개변수로 주어질 때, 문자열 before의 문자 순서를 변경하여 after 가 될 수 있다면 true 이며 아니라면 false 를 반환하세요."

 

문자열의 순서를 바꾼다는건 단순히 뒤집는다는 이야기가 아니라, 모든 순서를 바꾸는 방식을 동원한다는 의미이고, 다른말로 두 매개변수의 문자 종류와 갯수가 동일하다면, true 라고 해도 된다. 왜냐하면 여기서 순서를 바꾸는 방식을 물어본것은 아니니깐.

 

그렇기 때문에, Map 을 활용하여 before 의 문자들을 key 값으로 가지고, 개수를 value 로 가지는 형태로 변경해준 다음, after 와 비교하면서 일치되는 문자는 하나하나 Map 의 값에서 지워나가는 방식으로 풀어보면 될 거 같다.

function solution(before, after) {
    let map1 = new Map();
    before.split("").forEach((v) => { map1.get(v)? map1.set(v, map1.get(v) + 1) : map1.set(v, 1)});
    after.split("").forEach((v) => {
        if(map1.has(v)){
            map1.set(v, map1.get(v) - 1); 
        }
        if(map1.get(v) === 0){
            map1.delete(v);
        }
    })
    return map1.size ? 0 : 1
    
}

다른 방식을 사용할 수 있었지만, Map 을 활용하여 sort 를 사용하지 않고 시간복잡도 n 을 유지할 수 있게 되었다. forEach 를 통해 문자열 길이 n 만큼 순회를 하겠지만, map 에 key 와 value 를 생성 및 참조하는 과정, 그리고 값을 지우는 과정들에서 모두 시간복잡도 O(1) 을 가지기 때문에, 또한 size 체크 역시 O(1) 이기 때문에, 현 솔루션은 최종적으로 O(n) 을 가지게 될 것이다. (맞을거다...) 

반면 sort 를 활용하면 O(nlogn)의 복잡도를 가지기 때문에, 좀 더 비효율 적이라 판단하였다.

---

Set 의 특징은?

앞에서 기본적으로 Map 자료구조에 대해 살펴보았고, 이제 Set 자료구조에 대해 살펴보자.

 

우선, Set 은 Map 과 달리 key 가 없는 값이 저장이 된다. 이와 동시에 두 자료구조의 가장 큰 차이는 Set 의 경우 중복된 key 를 허용하지 않는다는 점에 있다. 이 부분이 상당히 유용하게 사용될 수 있다. 코드로 살펴보자

// set 을 생성한다.
let set = new Set();

let john = { name: "John" };
let pete = { name: "Pete" };
let mary = { name: "Mary" };

// map과 차이점은 add 를 통해서 추가한다는 점이다.
set.add(john);
set.add(pete);
set.add(mary);
// 반복하여서 key 값을 동일하게 추가하였다. 
set.add(john);
set.add(mary);

// 셋에는 유일무이한 값만 저장된다. 이게 아니라면 5 였어야 한다.
alert( set.size ); // 3

// 역시나 map 과 동일하게 이터러블 하다.
for (let user of set) {
  alert(user.name); // // John, Pete, Mary 순으로 출력. 역시나 입력순서에 따라 순회를 돈다.
}

대부분의 특징은 Map 과 유사하지만, 중복을 허용하지 않는다는 점에서 특정 상황에 유리하게 작용할 수 있다. 주요 메서드는 아래와 같다.

 

• set.add(value) : 값을 추가하고 셋 자신을 반환
• set.delete(value) : 값을 제거. 값이 셋에 있다면 true, 없다면 false 를 반환(if에 활용할 수 있다)
• set.has(value) : 셋 내에 값이 존재한다면 true, 아니면 false 를 반환
• set.clear() : 셋을 비운다.
• set.size : 셋의 요소 개수를 나타낸다.

Set 에 값에 반복 작업하기

for..of 나 forEach 를 사용하여 셋의 반복 작업을 할 수 있다.

// 만약 배열안에 중복된 요소가 있다면, 그 요소는 1개를 제외하고 모두 사라진다.
let set = new Set(["oranges", "apples", "bananas"]);

for (let value of set) alert(value);

// forEach를 사용해도 동일하게 동작한다
set.forEach((value, valueAgain, set) => {
  alert(value);
});

Set 은 키가 없는 값이 저장이 되지만, (그래서 위에서 for..of 문에서 그냥 set 를 가져와서 사용) 메서드 자체는 Map 과 동일하다. 다만 set.keys() 와 set.values() 는 동일한 기능을 하게된다. Map 과 호환을 맞추기 위해 있는 것일 뿐.

 

간단한 예시를 통한 Set 의 활용 방법

프로그래머스 level.1 문제 : 폰켓몬

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

프로그래머스

문제는 길어서... 들어가서 참고하자.

 

요약하자면, 주어지는 배열의 절반 만큼 숫자를 가져갈 때, 이때 가져간 숫자들의 최소 중복값을 반환하면 된다.

Set 을 이용하면 간단해진다. 주어지는 배열을 복사하여(얕은), 이 복사된 배열의 중복된 숫자들을 다 하나씩 남도록 변경해준다. 이 다음 이 Set 의 size 나 length 를 측정하여, 배열의 절반을 넘게 되면 배열의 절반길이를 반환하고, 아니라면 Set 의 size를 반환하면 된다.

function solution(nums) {
  let maximum = nums.length / 2;
  let setNums = [...new Set(nums)];

  return setNums.length > maximum ? maximum : setNums.length;
}

---

알고리즘 문제를 풀다가 사용하게 된 개념이라 간단하게 정리해보았다. Map, Set 의 경우 정리한 내용보다 더 많은 점들이 있지만 우선은 여기까지 포스팅 하겠다.

 

앞으로도 공부 중 배운 내용들을 추가로 정리해보겠다.