[알고리즘] leetcode 8월

- 알게 된 게 많았던 것 위주로 정리

- 내가 푼 정답이 성능이 잘 나왔던 경우도 있지만... 대부분 성능이 그다지 좋지 못해서 discuss를 많이 참고했다.

 

 

1. Longest Substring Without Repeating Characters

 

 

- 문제: 중복되는 문자가 없는 가장 긴 subString의 길이를 반환하는 문제.

- 해결: window sliding 기법, Map 자료구조 사용

 

 

// * 중복된 문자가 들어가지 않는 가장 긴 subString을 출력하는 문제

// ! window sliding 기법 + Map 을 사용하여 해결

const legnthOfLongestSubString = (s) => {
    let stringMap = new Map();
    let left = 0;
    let maxLength = 0;

    for (let right = 0; right < s.length; i++) {
        if (stringMap.has(s[right])) {
            maxLength = Math.max(maxLength, right - left);
            left = Math.max(stringMap.get(s[right]) + 1, left);
        }

        stringMap.set(s[right], right);
    }
    maxLength = Math.max(maxLength, s.length - left);

    return maxLength;
};

 

 

 

 

 

2.  Longest Palindromic Substring

 

- 문제: 대칭된 문자열 중 가장 긴 subString을 출력하는 문제

- 해결: DP

 

// https://leetcode.com/problems/longest-palindromic-substring/discuss/428331/Javascript-DP
// 참고한 solution

// * 거꾸로 해도 똑같은 문자열 중 가장 긴 subString을 출력하는 문제

// ! DP -> 차츰 true의 범위를 넓혀가며 출력

const longestPalindrome = (s) => {

    if (s.length <= 1) {
        return s;
    }

    const dpList = [...new Array(s.length + 1)].map(_=> new Array(s.length + 1).fill(false));
    // new Array(number) => 숫자를 넣으면 그만큼의 배열을 return
    // JS에서는 New Array 보다는 []로 배열을 초기화하는 것을 권장하고 있음.

    let longPS = '';

    // 1. 하나의 문자열은 각각 다 palindrome 이므로 true로 바꾸기
    for(let i = 0; i < s.length; i++) {
        dpList[i][i] = true;
        longPS = s[i];
    }

    // 2. 연속된 두개의 같은 문자열일 경우 palindrome이므로 true로 바꾸기
    for(let i = 0; i < s.length; i++) {
        if(s[i] === s[i+1]) {
            dpList[i][i+1] = true;
        }
        //그 다음 문자열이 trueaus longPS 바꾸기
        if(dpList[i][i+1]) {
            longPS = s.substring(i, i+2);
            // subString이 아니라 substring!
        }
    }

    // 3. 문자열을 넓혀가면서 palindrome인지 검사하기

    // i와 j는 각각 s 문자열의 범위를 뜻함 i ~ j 를 검사 
    // i 는 문자열 끝부터
    // j 는 i에서 두번 째 떨어진 문자 (하나 떨어진 문자열은 검사했으니까)
    for(let i = s.length-1; i >= 0; i--) {
        for(let j = i+2; j < s.length; j++) {
            // dpList[i+1][j-1] => i와 j사이의 문자열이 palindrome인지 검사 
            // s[i] === s[j] 면 palindrome i~j까지 palindrome
            s[i][j] = dpList[i+1][j-1] && s[i] === s[j];

            if(dpList[i][j]) {
                // 현재 lps의 길이가 기존의 lps길이보다 길면
                longPS = longPS.length < (j-i+1) ? s.substring(i, j+1) : longPS;
            }
        }
    }
    
    return longPS;
}

longestPalindrome("saefss");

 

 

 

 

3. Container With Most Water

 

- 문제 : 막대의 높이가 배열로 주어질때 가장 많은 물을 담의 양을 반환하는 문제

- 해결: two pointer

 

 

// * 최대한 많은 양의 물을 출력하는 문제 

// ! left right를 양 끝에 두고 하나씩 줄여오는 해결방법

const maxArea = (height) => {
    let left = 0;
    let right = height.length - 1;
    let water = 0;

    while(left < right) {
        const currentWater = (right - left) * Math.min(height[right], height[left]);

        height[right] > height[left] ? left++ : right--;

        if(water < currentWater) {
            water = currentWater;
        }
    }

    return water;
}

 

 

 

 

4. Valid Parentheses

 

- 문제: 유효한 괄호인지 검사하는 문제

 

- 알게 된 점

1.) while(s) 가 아니라 while(s.length > 0) 작성해주어야 무한루프 에러가 걸리지 않음

2.) 배열 요소를 검사하고자 할 때 어떤 메소드를 쓸지 고려해보기 

 

// * 유효한 괄호인지 확인하는 문제 

// ! 1. while문 돌릴 시 python 처럼 while(s)로 돌리면 무한 루프 걸림! 주의
// ! 2. if 에서 queue.pop()으로 매번 뽑아 비교하려고 하면 메모리 참조 오류 일어남
 var isValid = function(s) {
    s = s.split("");
    const open = ['{', '(', '['];
    const queue = [];
    
    
    while (s.length > 0) {
        queue.push(s.pop());
        const len = queue.length;
        
        if (open.includes(queue[len - 1])) {
            const lastBraket = queue.pop();
            const compareBraket = queue.pop();
            
            if (lastBraket === '(') {
                if(compareBraket !== ')') {
                    return false;
                }
            } else if (lastBraket === '{') {
                if(compareBraket !== '}') {
                    return false;
                }
            } else if (lastBraket === '[') {
                if(compareBraket !== ']') {
                    return false;   
                }
            }
        }
    }
    
    if(queue.length !== 0) {
        return false;
    }
    
    return true;
};

 

 

 

 

 

5. Generate Parenthses

 

- 문제: 유효한 괄호의 수를 모두 출력하는 문제

- 해결: 백트래킹

- 실수: 첫번 째 if문에서 s + ")" 가 아니라 s += ")"을 적어주면 두개의 if문에서 아래에 있는 if 문의 s가 영향을 받는다.

 

// * 숫자가 들어오면 해당 숫자 쌍만큼의 괄호를 모두 출력하는 문제 

// ! s += "("는 아래에 한 번 더 나오는 if문까지 영향을 주게 됨

 var generateParenthesis = function(n) {
    const res = [];
    
    const go = (l, r, s) => {
        if (s.length === n * 2) {
            res.push(s);
            return;
        }
        
        if(l < n) {
            go(l+1, r, s + "(");
        }
        
        if(r < l) {
            go(l, r+1, s + ")");
        }
    }
    
    go(0, 0, "");
    
    return res;
};

 

 

 

 

 

6. Swap nodes in pairs

 

문제: linked list로 주어진 리스트를 한 쌍(두개)씩 뒤집는 문제

알게 된 점: linked list는 length 등의 방법으로 길이를 구하지 못한다

 

// ! disscusion

const go = (head) => {
    if(!head || !head.next) {
        return head;
    }
    
    const prev = head;
    const center = head.next;
    const next = center.next;

    center.next = prev;
    prev.next = go(next);
    return center;
}

 

 

 

 

 

7. Next Permutation

 

- 문제: 사전적 순서상 다음 숫자배열을 찾는 문제

 

// * 사전 숫서상 다음 숫자를 찾는 문제 

// ! end에서 부터 처음으로 감소하는 값을 찾음 (이전 값은 계속해서 증가해온 값)
// ! 그 다음으로 큰 수를 찾아서 바꾸고 우측 정렬을 해줌
// ! in plcae라서 들어온 nums만 가지고 바꾸는 문제 


var nextPermutation = (nums) => {
    for(let i=nums.length-1; i>=0; i--) {
        if(nums[i] < nums[i+1]) { // 뒤에서 최초로 감소하는 수
            const large = nextLarge(i); // 최초로 감소하는 수의 오른쪽에서부터 i보다 큰 값
            swap(i, large);
            reverse(i+1);
            return;
        }
    }

    nums.reverse();

    const nextLarge = (idx) => {
        for(let i=nums.length-1; i > idx; i--) {
            if(nums[i] > nums[idx]) {
                return i; // 최초로 감소하는 수니까... 그 전까진 계속 커지기만 했을 거임!
            }
        }
    }

    const swap = (i, j) => {
        return [nums[i], nums[j]] = [nums[j], nums[i]];
    }

    const reverse = (start) => {
        const end = nums.length - 1; 

        while(start < end) {
            swap(start, end);
            start++;
            end--;
        }
    }
}

 

 

 

 

 

8. Search In Rotated Sorted Array

 

문제: 순회되는 배열에서 특정값을 찾는 문제

 

 

// * 두 가지 경우 =>
// * 1.  nums[left] > nums[mid]
// * 2.  nums[left] < nums[mid]
// * 이 경우, target의 범위를 비교하여 left 와 right의 범위를 옮겨주면 끝

const search3 = (nums, target) => {
    let left = 0;
    let right = nums.length - 1;

    while (left <= right) {
        let mid = Math.floor((left + right) / 2);

        if (nums[mid] === target) {
            return mid;
        }

        if (nums[left] < nums[mid]) {
            // ! 왼쪽에 있는 수가 mid 값보다 작은 경우
            if (nums[left] <= target && target < nums[mid]) {
                // * left & mid 사이 target이 있으면
                right = mid - 1; // * right 범위를 옮김
            } else {
                // * left 범위를 옮김
                left = mid + 1;
            }
        } else {
            // ! 왼쪽이 mid 값보다 큰 경우
            if (nums[left] <= target || target < nums[mid]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
    }

    return -1;
};

 

 

 

 

 

9. Find First and Last Position of Element in Sorted Array

 

- 문제: 오름차순 배열에서 target number의 첫번째와 끝 인덱스를 찾는 문제

const search = (nums, target) => {
    let left = 0;
    let right = nums.length - 1;

    while(left <= right) {
        const mid = Math.floor((left + right) / 2);

        if (target === nums[mid]) {
            left = mid;
            right = mid;
            while (nums[left - 1] === target || nums[right + 1] === target) {
                

                if (nums[mid + 1] === target) {
                    right++;
                }

                if (nums[mid -1 ] === target) {
                    left--;
                }
            }
            return [...left, ...right];
        }

        if (mid === left && mid === right) { // while을 빠져나왔는데도 찾는게 없음
            return [-1, -1];
        }

        if( target < nums[mid]) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }

    }
}

 

 

 

 

 

10. Search Insert Position

 

- 문제: 주어진 배열에 특정 숫자의 삽입할 인덱스의 위치를 찾는 문제

 

var searchInsert = function(nums, target) {
    return binarySearch(nums, target, 0, nums.length - 1);
};

function binarySearch(array, target, start, end) {
    if(start > end) {
        return start;
    }
    
    const mid = Math.floor((start + end) / 2);
    
    if(array[mid] === target) {
        return mid;
    }
    
    if(target > array[mid]) return binarySearch(array, target, mid+1, end);
    if(target < array[mid]) return binarySearch(array, target, start, mid-1)

}

 

 

 

 

 

11. Combination Sum 

 

- 문제: 특정 숫자를 이루는 배열요소의 모든 조합을 출력하는 문제

- JS의 깊은 복사, 얕은 복사에 대해 배웠다...! 

 

 

// * backtracking
var combinationSumFun = function (candidates, target) {
  const res = [];

  const go = (index, target, nums) => {
    nums.push(candidates[index]);
    target = target - candidates[index];

    if (target <= 0) {
      if (target === 0) {
        res.push(nums);
      }
      return;
    }

    for (let i = index; i < candidates.length; i++) {
      go(i, target, nums.slice());
      // * 백트래킹으로 푸는 문제...  nums를 그대로 넘겨주면 nums는 이미 nums.push(num)의 상태이므로
      // * 백트래킹으로 돌아와도 nums의 값은 num의 값이 추가되어 기존의 값이 변동된다
      // ! 이때 slice()는 복사한 값을 넘겨줌으로써 백트래킹을 가능하게 만든다.
    }
  };

  for (let i = 0; i < candidates.length; i++) {
    go(i, target, []);
  }
  return res;
};

 

 

 

 

 

12. Jump Game 2

 

- 문제: 각 배열의 수가 해당 인덱스로부터 가능한 점프 횟수를 나타내고, 마지막 요소까지 도달 가능할때 최소한의 점프 수

- 해결: 그리디 기법

 

//* greedy
var jump = function(N) {
    let count = 0;
    let currMax = 0;
    let nextMax = 0;

    for(let i=0; i<N.length; i++) {
        nextMax = Math.max(N[i] + i, nextMax);

        if(i === currMax) {
            count++;
            currMax = nextMax;
        }
    }

    return count;
};

 

 

 

 

 

13. Permutations

 

- 문제: 주여진 배열로 가능한 모든 조합을 출력하기

- splice와 slice의 차이에 대해 알게 되었다

 

 

 var permute = function(nums) {
    const res = [];
    
    const go = (permutations, numbers) => {
        if (!numbers.length) {
            res.push(permutations);
            return;
        }
        
        for(let i=0; i<numbers.length; i++) {
            const copy = numbers.slice(); // *깊은 복사
            copy.splice(i,1);
            go([...permutations, numbers[i]], copy);
        }
    }
    
    go([], nums);
    
    return res;
};

 

const nums = [1,2,3,4,5,6];

const numSlice = nums.slice(1,4);
console.log(numSlice)
console.log(nums);

const numSplice = nums.splice(1, 4);
console.log(numSplice);
console.log(nums);