두시간 알고리즘 - 1일차, 오늘은 LeetCode Weekly Context 241 푼다

오늘은...

오늘은 문제푼다. 

https://leetcode.com/contest/weekly-contest-241

Contest - LeetCode

 

 

1. 부분집합을 구하는 문제: 34m30s29

https://leetcode.com/problems/sum-of-all-subset-xor-totals/

Sum of All Subset XOR Totals - LeetCode

/**
 * @param {number[]} nums
 * @return {number}
 */
var subsetXORSum = function(nums) {
    let answer = 0; 

    function recursive(index, acc){  
        if(index === nums.length){
            return;
        }
        
        answer += acc ^ nums[index];
        recursive(index+1, acc ^ nums[index]);
        
        recursive(index+1, acc);
    }
    
    recursive(0, 0); // 0번째 원소 포함
  
    return answer;
};

부분집합 구하는 문제는 매번 머리속이 어떻게 된건지 좀 복잡하게 접근하게 되는 경향이 있다. 

기억합시다. 부분집합은 기본적으로 index번째 원소를 포함시킬거냐, 안시킬거냐만 기억하면 된다. 

 

기본적으로는 흐름은 재귀함수를 호출하면서 index번째 원소 포함하니, 안하니가 포인트이다. 

이문제에서는 실제로 어떤 부분집합인지 구하는 것 보다는 내가 포함될지 안될지 결정할때 그 앞에 누적되어있는 부분집합의 xor합에 다가 누적해서 계산하면된다. 

 

헷갈렸던 부분은 xor이라 처음 원소를 선택할때 0 xor something 이렇게 했을때 이상한값이 나오면 어쩌지했는데 0 xor something = 내something 이다. 

 

 

2. swap 하는 횟수 구하는 문제 30m06s42

https://leetcode.com/problems/minimum-number-of-swaps-to-make-the-binary-string-alternating/

Minimum Number of Swaps to Make the Binary String Alternating - LeetCode

/**
 * @param {string} s
 * @return {number}
 */
var minSwaps = function(s) {
    // either 101010.... 0101010....
    
    let startWithOne = {0: 0, 1: 0}; // 위치가 틀린애들 체크
    let startWithZero = {0: 0, 1: 0};
    
    Array.from(s).forEach((target, index) => {
        if(index % 2 === 0){
            // index 짝수번째 숫자
            if(target === '1'){
                startWithZero[1]++;
            }else if(target === '0'){
                startWithOne[0]++;
            }
        }else{
            // index 홀수번째 숫자
            if(target === '1'){
                startWithOne[1]++;
            }else if(target === '0'){
                startWithZero[0]++;
            }
        }
    });
    
    let answer = -1;
    if(startWithOne[0] === startWithOne[1]){
        answer = startWithOne[0];
    }
    
    if(startWithZero[0] === startWithZero[1] && (answer === -1 || answer > startWithZero[0])){
        answer = startWithZero[0];
    }
    
    return answer;
};

가끔은 그런 의문이 있다. 개발을 접어야하는것은 아닐지. 여튼 이문제도 엄청 어려운건 아니었으나 결과론적으로는 삽질을 조금했다. 

 

길이 n의 1과 0으로만 구성된 string이 주어졌을때 1010101... 010101...으로 바꿀수있도록 숫자를 몇번 swap해야하는지 구하는 문제이다. 

 

그래서 1로 시작할때 기준으로 잘못된 자리를 잡고있는 0,1의 갯수를 세고, 0으로 시작할때 잘못된 자리를 잡고 있는 0, 1의 갯수를 센다. 그리고 이게 둘이 서로 같아야만 swap을 해서 숫자를 만들수 있기때문에 길이가 같은지 체크해주고 더 적게 바꿔도 되는 것을 답으로 반환한다. 

 

 

3. 특정 sum을 이루는 pairs의 갯수 구하기: 49m42s6

https://leetcode.com/problems/finding-pairs-with-a-certain-sum/discuss/

Finding Pairs With a Certain Sum - LeetCode Discuss

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 */
var FindSumPairs = function(nums1, nums2) {
    this.nums1 = nums1;
    this.nums2 = nums2;
    
    // nums1의 값별 인덱스
    this.cache1 = {};
    for(let i = 0; i < this.nums1.length; i++){
        if(!this.cache1[this.nums1[i]]){
            this.cache1[this.nums1[i]] = { index: i, count: 1};
        }else{
            this.cache1[this.nums1[i]].count++;
        }
    }
    
    // nums2를 값별로 cache
    this.cache2 = {};
    for(let i = 0; i < this.nums2.length; i++){
        if(!this.cache2[this.nums2[i]]){
            this.cache2[this.nums2[i]] = { index: i, count: 1};
        }else{
            this.cache2[this.nums2[i]].count++;
        }
    }
};

/** 
 * @param {number} index 
 * @param {number} val
 * @return {void}
 */
FindSumPairs.prototype.add = function(index, val) {
    this.cache2[this.nums2[index]].count--; // 갯수를 줄인다
    
    this.nums2[index] += val; 
    
    if(!this.cache2[this.nums2[index]]){
        this.cache2[this.nums2[index]] = { index: index, count: 1};
    }else{
        this.cache2[this.nums2[index]].count++;
    }
};

/** 
 * @param {number} tot
 * @return {number}
 */
FindSumPairs.prototype.count = function(tot) {
    let answer = 0;
    
    for(const [key, value] of Object.entries(this.cache1)){
        const one = key;
        const two = `${tot - +key}`;
        
        if(this.cache1[one] && this.cache2[two]){
            answer += (this.cache1[one].count * this.cache2[two].count);
        }
    }
    
    return answer;
};

/** 
 * Your FindSumPairs object will be instantiated and called as such:
 * var obj = new FindSumPairs(nums1, nums2)
 * obj.add(index,val)
 * var param_2 = obj.count(tot)
 */

이문제는 계산횟수를 최대한 줄이는 것이 까탈스러운 문제였다. 

 

나는 cache1에 nums1의 값에 따라사 등장횟수를 구하고(count property), cache2도 그와 같이 구했다. 하지만 cache2의 경우 add동작에 따라 값이 변하기 때문에 add에서 값이 변하면 기존의 값의 count를 줄이고, 새로 변경된 값에 대해서 cache2값을 업데이트해주었다. 

 

count를 할때는 cache1의 프로퍼티를 순회하면서 만약에 이때 값이 1이라면, nums2에서는 tot-1인 것들의 갯수를 구해야한다. 이때 두 값이 모두 있다면 answer의 각각의 카운트를 곱해서 넣는다. 왜냐하면 pair의 수를 구하는 것이기 때문에. 

 

이때 nums1은 최대 길이가 1000이라서 1000개의 count 명령이 입력되도 복잡도는 대략 1000 * 1000정도라 시간초과가 안걸린다. 

 

근데 속도가 9.46프로 정도라 다른 사람들은 뭐하는 사람들인가 싶어서 봤더니 map을 사용하고 있었다. 그리고 nums1을 정렬해서 사용하고 잇었다. 그래서 1000번을 항상 안돌고 중간에 끊을 수 있도록. 

 

Map으로 바꿔보았다. 

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 */
var FindSumPairs = function(nums1, nums2) {
    this.nums2 = nums2; 
    // nums1의 값별 인덱스
    this.cache1 = new Map();
    
    for(let i = 0; i < nums1.length; i++){
        if(!this.cache1.has(nums1[i])){
            this.cache1.set(nums1[i], 1);
        }else{
            this.cache1.set(nums1[i], this.cache1.get(nums1[i])+1);
        }
    }
    
    // nums2를 값별로 cache
    this.cache2 = new Map();
    for(let i = 0; i < this.nums2.length; i++){
        if(!this.cache2.has(this.nums2[i])){
            this.cache2.set(this.nums2[i], 1);
        }else{
            this.cache2.set(this.nums2[i], this.cache2.get(this.nums2[i])+1);
        }
    }
};

/** 
 * @param {number} index 
 * @param {number} val
 * @return {void}
 */
FindSumPairs.prototype.add = function(index, val) {
    this.cache2.set(this.nums2[index], this.cache2.get(this.nums2[index])-1); // 갯수를 줄인다
    
    this.nums2[index] += val; 
    
    if(!this.cache2.has(this.nums2[index])){
        this.cache2.set(this.nums2[index], 1);
    }else{
        this.cache2.set(this.nums2[index], this.cache2.get(this.nums2[index])+1);
    }
};

/** 
 * @param {number} tot
 * @return {number}
 */
FindSumPairs.prototype.count = function(tot) {
    let answer = 0;
    
    for(const [key, value] of this.cache1.entries()){
        const one = key;
        const two = tot - +key;
    
        if(this.cache2.get(two)){
            answer += (value * this.cache2.get(two));
        }
    }
    
    return answer;
};

/** 
 * Your FindSumPairs object will be instantiated and called as such:
 * var obj = new FindSumPairs(nums1, nums2)
 * obj.add(index,val)
 * var param_2 = obj.count(tot)
 */

그랬더니 엄청난 속도로 개선이 되었다. 

 

https://stackoverflow.com/questions/18541940/map-vs-object-in-javascript#:~:text=Maps%20can%20be%20slower%3A&text=An%20object%20behaves%20like%20a,keys%20instead%20of%20just%20strings.

Map vs Object in JavaScript

이 글을 읽어보니, iterate해야하는 경우에는 map을 사용하는 것이 좋은 것 같다. 이번에 봤듯이 속도도 훨신 빠르다. 

 

후기

오랜만에 LeetCode 문제풀이를 했더니 좀 재미있었던것 같다.