자바스크립트 릿코드 #3 Contains duplicate

들어가며

이 포스팅에서는 leetcode 추천 문제 top 75를 자바스크립트로 풀어보며 자바스크립트 공부와 알고리즘 공부를 동시에 합니다. 문제와 풀이를 적을 건데, 틀린 부분이나 더욱 개선될 부분이 있다면 댓글로 달아주시면 정말 감사하겠습니다.

문제

Contains Duplicate

문제 설명

문제 개요

이 문제는 일반적인 언어들에 구현된 배열의 contains 함수와 같은 기능(배열에 중복이 있는지)을 직접 구현해보는 문제 입니다.

예제

입력: [1,2,3,1]
출력: true

입력: [1,2,3,4]
출력: false

입력: [1,1,1,3,3,4,3,2,4,2]
출력: true

풀이 과정

자료구조를 이용하면 쉽게 풀릴 것 같다는 생각을 바로 했습니다.

자바에서 자주 쓰는 Object를 이용해서 숫자를 key로 부여하고, true, false를 value로 부여하면 괜찮겠다는 생각을 했습니다.

바로 구현을 했고, 매우 좋은 결과가 나왔습니다.

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var containsDuplicate = function(nums) {
    let map = {};
    
    for(let i=0; i<nums.length; i++){
        if(map[nums[i]]){ // maybe undefined
            return true;
        }else{
            map[nums[i]] = true;    
        }
    }
    
    return false;
};

그리고 여러가지 다른 풀이가 있었는데 재밌는 풀이법들은 한줄 풀이법들이었습니다.

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var containsDuplicate = function(nums) {
    return new Set(nums).size < nums.length;
};

Set 자료구조를 이용한 풀이법이 있을 수 있겠다 생각은 했는데 의외로 한줄로 이렇게 짧게 나올 줄은 몰랐습니다. 역시 자바스크립트라는 언어의 힘인 것 같습니다.

성능도 Object를 이용한 것이랑 큰 차이가 없었습니다.
공간복잡도는 Set을 이용한 것이 훨씬 좋았습니다. 아마 Set 자료구조의 경우 Key Value에서 Value에 대해 제한이 있는만큼 뭔가 적게 차지하게 만들 수 있는 것 같습니다.

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var containsDuplicate = function(nums) {
    return nums.sort().some((a, i) => a === nums[i - 1]);
};

이 풀이에는 sort와 some이 쓰였는데, 둘 다 배열에서 유용하게 쓰일 수 있는 Array의 메소드들입니다. 위의 풀이는 배열을 먼저 [1, 2, 3, 4, 4, 5]와 같은 형태로 정렬한 뒤에 자신의 전 엘리먼트가 자신과 같다면(중복이 발생했다면), true를 리턴합니다.

배운 점

Array 메소드 중에 재밌는 것들이 많습니다.

some과 sort는 언제든 쓸 일이 많을 것 같습니다.