[알고리즘 스터디] Two Sum - MutableMap, HashMap

1. Two Sum

nums: IntArray와 target: Int가 주어지면 nums안의 두 원소를 합해 target이 되는 원소의 index번호를 찾는 문제다.

class Solution {
    fun twoSum(nums: IntArray, target: Int): IntArray {
        for (i in nums.indices) {
            for (j in i + 1 until nums.size) {
                if (nums[i] + nums[j] == target) {
                    return intArrayOf(i, j)
                }
            }
        }
        return intArrayOf()
    }
}

그동안 편한대로만 배열을 사용하다보니 배열을 순회하며 어떤식으로 활용하는게 좋을지 헷갈였다.
역시 자주자주 문제를 풀어줘야 머리가 굴러가는 듯 하다.

2중 for문을 사용해 간단하게 해결했다.

leet code의 상위 시간복잡도를 확인해보니 HashMap을 통해 값을 저장하며 시간복잡도를 줄였는데 큰 차이가 없는거같아서 그냥 이렇게 풀었다.

// 시간복잡도 160ms 코드 HashMap에 현재값을 저장하며 타깃에서 현재값을 뺀게 HashMap에 존재하는지 확인한다.

class Solution {
    fun twoSum(nums: IntArray, target: Int): IntArray {
        val sums = HashMap<Int, Int>();
        for(i in nums.indices) {
            val substractor = target - nums[i]
            if(sums.containsKey(substractor)) {
                return intArrayOf(sums.getOrDefault(substractor, i), i)
            }
            sums.put(nums[i], i)
        }
        return intArrayOf()
    }
}

생각보다 배열에 관련된 문제들에 HashMap을 활용하는게 많이 등장해서 MutableMap과의 차이가 궁금해져 한 번 알아보기로 했다.

Map, MutableMap

우선 Map은 Key와 Value를 통해 데이터를 저장하는 형태의 자료구조를 말하는데, Kotlin에서는 Map과 MutableMap은 모두 인터페이스로 구현체가 있어야 사용이 가능하다.

val map = Map<Int, Int> () // 사용불가X: 인터페이스기 때문에 객체가 생성되지 않는다.
val mutableMapt = MutableMap<Int, Int> ()

하지만 우리가 코드를 작성하며 심심치않게 mapOf()나 mutableMapOf()를 사용해서 Map을 구현하고는 한다.

그럼 대체 mapOf(), mutableMapOf()는 뭐고 hashMapOf()랑 뭐가 다르길래 다른 메서드를 사용하는걸까?

HashMap, LinkedHashMap

우선 Hash Map과 Linked Hash Map에 대해 알아보자, 두 타입 모두 해시함수를 통해 해시값을 생성한뒤 해당 값을 통해 생성된 해시코드를 기준으로 데이터의 위치를 결정한다.

하지만 해시코드로 생성된 버킷에 어떤 값이 저장되는지에 따라 Hash Map과 Linked Hash Map으로 나뉘게 되는데,Hash Map에는 단순 데이터가 담기는 반면, Linked Hash Map에는 Linked List처럼 이전에 저장된 값에 대한 포인터가 함께 담기게된다.

그 결과 Hash Map은 순서에 대한 정보가 없기 때문에 모든 값을 불러올 경우 매번 순서가 달라지게 된다.

하지만 Linked Hash Map의 경우에는 이전 값에 대한 포인터가 함께 저장되어 있기 때문에 값을 입력한 순서가 유지되고 그에 따라 늘 같은 순서대로 값이 불러와지게된다.

어떨때 어떤걸 써야할까?

이렇게만 보면 대체 두개가 어떤 차이가 있는지 잘 모르겟고, 어떨때 어떤걸 써야할지 잘 모르겠다. 그래서 비교해보았다 어떻게 다를까?

1. 순서 보장

두 타입의 가장 큰 차이점은 순서 보장 여부이다. 만약 데이터를 저장하면서 순서대로 저장하고 불러오는게 중요하다면 Linked Hash Map을 사용해야 할것이다.

2. 성능

순수하게 성능이 어떻게 다를지 궁금해서 성능에대한 테스트를 진행해봤다.
테스트 조건은 각각 10만개와 100만개의 Int값을 Hash Map과 Mutable Map(Linked Hash Map)에 삽입 / 검색 / 삭제하는데 걸리는 시간을 100회씩 반복해 측정해 평균을 내보았다. 각각 성능차이는 미세했지만 Mutable Map쪽이 약간 우세했다.

[10만개 * 100회]

• 삽입
  - Hash Map : 7.65 ms
  - Mutable Map : 5.04ms
  
  
• 검색
  - Hash Map : 9.49 ms
  - Mutable Map : 3.72ms
  
  
• 삭제
  - Hash Map : 2.07 ms
  - Mutable Map : 1.81ms

[100만개 * 100회]

• 삽입
  - Hash Map : 218.44 ms
  - Mutable Map : 146.17ms
  
  
• 검색
  - Hash Map : 176.46 ms
  - Mutable Map : 95.44ms
  
  
• 삭제
  - Hash Map : 69.24 ms
  - Mutable Map : 75.76ms

ms단위의 차이라 1000만 단위의 데이터는 되어야 초단위 차이가 나기는 하지만 확실히 Linked Hash Map쪽이 Hash Map에 비해서는 빨랐다.

그렇다면 알고리즘 문제를 풀때는 빠른 Linked Hash Map을 사용하지 않고 왜 Hash Map을 사용할까?

3. 메모리 차지

앞서 알아봤듯 Linked Hash Map의 경우 값을 저장하며 이전 값에 대한 포인터를 함께 저장한다. 그말은 포인터를 위한 메모리를 추가적으로 사용해야한다는 뜻이된다.

그래서 과연 메모리사용량이 얼마나 차이날지 테스트 해봤다.
(Int타입 값 100만개 기준)

• 데이터 생성 전 메모리 사용량 : 약 23MB
  
  
• Hash Map 생성 후 : 약 76MB (약 53MB 사용)
• Mutable Map 생성 후 : 약 162MB (약 86MB 사용)
  
  
• 검색시 : 둘 다 변동없음(메모리를 차지하고 있는 상태임)
  
  
• Hash Map 삭제 후 : 약 98MB (약 64MB 추가)
• Mutable Map 삭제 후 : 약 13MB (약 85MB 추가)

단순 Int타입의 값 100만개 기준으로는 Mutable Map이 약 1.4~1.5배정도 메모리를 더 많이 차지했다.

이를 보았을 때 시간복잡도와 공간복잡도 모두 상위권을 노려야하는 Leet Code의 특성상 자료의 삽입 순서가 중요하지 않다면, Hash Map을 사용하는게 타당해보인다.