LeetCode 219. Contains Duplicate II

금일 알고리즘 문제는 leetcode의 ’219번 Contains Duplicate II’문제였습니다. 이 문제를 자습때 복습하면서 삽질한 경험을 바탕으로 회고를 작성해보았습니다.

문제에서 구해야되는 것은 ’주어지는 배열에서 k만큼의 크기를 잘랐을 때 중복되는 값이 있는가?’입니다. 따라서 “주어지는 배열 ’nums’를 k만큼 자르고, 중복되는 것을 찾으면 되겠다.“라고 생각하여 문제에 들어갔습니다.

배열을 자르기 위해서 가장 먼저 떠올랐던 것은 js의 slice()메서드였습니다. slice메서드는 slice(0, 2)로 넣게되면, 인덱스 0부터 2까지 자르지 않고 0부터 1까지 잘라 반환하는 메서드입니다. 주어진 전제에서는 k만큼의 크기를 자르면되기 때문에 반복문과 함께 대략 slice(index=0++, index+k+1)이런 식의 흐름으로 생각하면 됩니다.

이제 남은 것은 ’잘린 배열내에서의 비교’입니다. 이걸 for문으로 단순하게 돌자니, 시간복잡도가 많이 소요될 것 같았습니다. ‘어떻게 해야하지?’ 고민하다가 AI의 추천을 받아 js에 내장된 ’Set’이라는 클래스를 알게 되었습니다.

Set의 독특한 점은 특별한 로직을 구현하지 않아도 Set 클래스로 정의된 객체는 ’원소의 중복을 허용하지 않는다’는 점이었습니다. 이러한 Set의 특징을 활용해 잘린 배열을 Set의 클래스로 정의였습니다. new Set(sliced_arr) 핵심은 set은 중복 원소를 허용하지 않기 때문에 정해진 크기로 잘린 배열의 길이보다 작아질 것이라는 특징을 활용했습니다. 결국 이와같은 조건으로 하여 true를 반환하는 로직을 세웠습니다. -> new Set(sliced_arr).size !== sliced_arr.length

검증을 위해 돌려보았는데, 치명적인 timeout 버그가 발생했습니다. timeout에 걸리지 않기 위해 for문 대신 Set을 사용했기에 생각하지 못했던 문제가 발생했던 것이었습니다.

저는 한 가지 간과했던 사실이 있었습니다. 중첩 for문을 방지하기 위해 사용했던 Set 클래스가 for문 내부에서 비교를 위해 ’new Set(sliced_arr)’로 계속 생성되고 있던 것이었습니다. 따라서 전체 플로우를 뒤집었습니다.

우선 for문 내부에서 비교를 위해 실행되던 Set을 for문의 바깥으로 옮겼습니다. ‘어떻게 하면 Set을 계속 생성하지 않고 비교하지?’ 고민하다가 떠오른 것은 ’교체’였습니다. 즉, ‘오래된 원소를 다음 인덱스의 원소로 갈아끼우면 되겠다. 어차피 순서는 중요하지 않으니까.’ 였습니다.

로직을 바꿨던 것이 문제를 이렇게 간단하게 해결할 수 있었습니다.

해결 과정

우선 Set 클래스의 객체를 선언한다 -> const set = new Set();
for문으로 배열(nums)의 원소를 탐색하여 set 내부에 원소가 있으면 즉시 true를 반환한다. -> if ( set.has(nums[index])) return true;
그렇지 않은 경우에 set에 nums[index]를 넣는다. -> set.add(nums[index]);
만약에 set의 길이가 k보다 커진다면, 가장 오래된 원소를 뺀다. -> if (set.size > k) set.delete(nums[index-k]);

이렇게 해주면 정상적으로 결과가 반환됩니다.

직관적으로 생각해서 쉽게 풀리는 문제들도 많았지만, 이렇게 다른 논리적인 해결방법도 익히는 것이 중요하다고 생각이 들었고, 결국엔 연습이 많이 필요한 과정이라고 생각이 들었습니다.

Map을 사용하여 해결하는 방법도 있었기에 Map으로도 구현을 시도해보았습니다.

Map의 특징으로는 금일 배웠던 TypeScript의 Record 타입과 매우 유사하게 (key, value)의 형태로 등록하고 반환할 수 있습니다. 이러한 Map의 특징은 곧 강점이 되기도 하는데요, ‘index를 구하시오’, ’value를 구하시오’와 같은 문제들은 거의 대부분 map으로 해결이 되기 때문입니다.

따라서 이번 문제도 Map으로 해결이 가능합니다. 그 전에 Map을 활용하는 방법은 총 2가지가 있는데요, 일반 ’Map ( key, value ) 형태’와 ’Hash Map ( value, key )’형태입니다. -> (해시맵도 (key, value)가 맞지만, 이해를 위해 value, key로 합니다.) 여기서 중요한 점은 이 방법이 선택하는 과정은 성능과 매우 밀접한 관련이 있다는 것입니다.

예를 들어 ’99라는 원소를 구하려는데 Map(인덱스, 숫자)로 구현하려고 한다.’라는 상황이라면, map은 ’어.. 99가 어디있더라..’하고 온 맵을 뒤집니다. 결국 불필요한 연산이 늘어나 성능 문제가 발생하곘죠. 이때의 시간복잡도는 최악의 경우에 O(n^2)이 될 수 있습니다.

반면에 HashMap으로 구현한 방식은 Map(숫자, 인덱스)이기 때문에 ’99라는 원소를 찾고싶어!’라는 요청이 오면, ’아 99는 1번에 위치해.’라는 응답을 바로 뱉습니다. 색인을 찾아 해당 값으로 바로 이동하기 때문에 시간복잡도는 O(n)이 되겠죠.

그러던 중 문득 ’어? 그냥 Map을 해서 indexOf()로 구현하면 되지않나?’가 생각이나서 indexOf()로도 구현해보았지만, indexOf()도 결국 내부에는 for문으로 돌아가기 때문에 최악의 경우 시간복잡도가 O(n^2)이 될 것입니다.

이렇게 삽질 과정을 거쳐 최종적으로 Hash Map으로 구현한 결과는 다음과 같습니다.

해결 과정

앞서 Set에서 했던 실수를 재범하지 않도록 for문 밖에서 Map클래스 객체를 선언하였습니다. -> const map = new Map();
for 반복문을 통해 마찬가지로 nums[index]가 map에 존재하는지 확인합니다. 이때 해당 조건이 ’참’인 경우에서 앞서 말한 HashMap의 강점이 드러납니다. -> let find_index=map.get(nums[index]);
i와 index의 차이가 k보다 작거나 같으면 true를 반환합니다. -> if(index-find_index) return true;
이후에 Map에 ( 숫자, 인덱스) HashMap 형식으로 추가합니다 -> map.set(nums[i], i);

이렇게 하나의 문제를 set과 map을 통해 다양한 삽질을 경험해보았는데요, 이번을 계기로 set과 map의 특징, 사용방법을 확실히 알게됐습니다. 그럼에도 여전히 중요한 것은 여러번 알고리즘 문제를 해결해보고 경험을 쌓는 것이라 생각합니다.