두시간 알고리즘 - 4일차, two pointer(1)

4일차..

https://leetcode.com/tag/two-pointers/

Two Pointers - LeetCode

 

- 기법 설명: https://velog.io/@adorno10/%ED%88%AC-%ED%8F%AC%EC%9D%B8%ED%84%B0-Two-Pointer 

투 포인터 (Two Pointer)

https://naivep.tistory.com/52

투 포인터스 알고리즘 (Two Pointers Algorithm)

절대 정답이 되지않는 경우를 skip하는 알고리즘이라고 한다. 

 

1. Remove Duplicates from Sorted Array: 28m02s33

https://leetcode.com/problems/remove-duplicates-from-sorted-array/

Remove Duplicates from Sorted Array - LeetCode

헙..내가 이런걸 풀수가 있다니.... 이게 되긴 되나보다.. 쉬운 문제라도 단순히 뭔가 조작해서 푸는 문제는 자신이없었는데 index 두개로 조작을 해야겠다, 확신을 가지니까 풀어진다. 

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

    for(let right = 1; right < nums.length; right++){
        if(nums[left] < nums[right]){
            let temp = nums[right];
            nums[right] = nums[left+1];
            nums[left+1] = temp;
            left++;   
        }
    }
    
    return left+1;
};

메모리 추가로 선언한거 무슨 변수하나뿐인데, 저렇게 나와서 다른사람들은 먼가 싶다. 

left, right를 통해서, left는 현재 정돈되어서 들어가있는데중에서 최대 인덱스고, right는 계속 검사하는 인덱스다. 정돈된거중에 가장 큰값보다, 더 큰값이 나오면 left보다 하나큰 인덱스에 해당값을 넣어준다. 그리고 left는 1증가. 이렇게 하면 배열을 추가로 할당하지 않고도 inplace에서 중복 제거가 가능하다. 

 

2. Longest Substring Without Repeating Characters: 25m25s10

https://leetcode.com/problems/longest-substring-without-repeating-characters/

Longest Substring Without Repeating Characters - LeetCode

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
    if(s.length === 0) return 0;
    
    const checker = {};
    
    let left = 0;
    let answer = 1;
    checker[s[left]] = 1;
    
    for(let right = 1; right < s.length; right++){
        if(checker[s[right]] && checker[s[right]] > 0){
            
            // 값이 추가된 적이 있을때
            while(left <= right && checker[s[right]] !== 0){
                checker[s[left]]--; // 현재꺼를 빼는 중
                left++;
            }     
            
        }
        
        // 1이라고 체크
        checker[s[right]] = 1;
        
        const len = right - left + 1;
        if(answer < len) {
            answer = len;
        }
    }
 
    return answer;
};

map으로 바꿔보았다.

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
    if(s.length === 0) return 0;
    
    const checker = new Map();
    
    let left = 0;
    let answer = 1;
    checker.set(s[left], 1) 
    
    for(let right = 1; right < s.length; right++){
        if(checker.has(s[right]) && checker.get(s[right]) > 0){
            // 값이 추가된 적이 있을때
            while(left <= right && checker.get(s[right]) !== 0){
                checker.set(s[left], checker.get(s[left]) - 1); // 현재꺼를 빼는 중
                left++;
            }     
            
        }
        
        // 1이라고 체크
        checker.set(s[right], 1);
        
        const len = right - left + 1;
        if(answer < len) {
            answer = len;
        }
    }
 
    return answer;
};

이제끝!

 

- 해설: 

https://www.youtube.com/watch?v=wiGpQwVHdE0 

해설을 보니까, Map까지 갈필요도 없고 Set을 하면 되는거였다!!! 다 때려넣어놓고 has인지 아닌지를 체크하면 된다. 

 

 

3. Container With Most Water: 32m48s31

https://leetcode.com/problems/container-with-most-water/

Container With Most Water - LeetCode

/**
 * @param {number[]} height
 * @return {number}
 */
var maxArea = function(height) {
    let left = 0; 
    let right = height.length - 1;
    
    let answer = 0;
    while(left < right){
        const area = (right - left) * Math.min(height[left], height[right]);
        if(answer < area){
            answer = area;
        }
        
        // 더작은 쪽이 인덱스를 바꿔야함, 같으면 바꿀 대상이 더 큰쪽으로
        if(height[left] < height[right]){
            left++;
        }else if(height[left] > height[right]){
            right--;
        }else{
            // 같을때
            if(height[left+1] > height[right-1]){
                left++;
            }else{
                right--;
            }
        }
        
    }
    
    return answer;
};

양끝에서부터, left, right를 체크하는데, 높이가 더 작은쪽부터 위치를 바꾸면된다. 높이가 같을때는, 둘중에 위치를 옮겼을때 더 높은애를 옮기도록 했다. 

 

그 이유는 중간에 무슨 막대가 있든 없든 너비는 양끝중에 작은애랑 두인덱스의 거리로 구해지기 때문. 큰쪽을 줄이면 항상 그전보다 더 작을수밖에 없다(두인덱스 사이의 거리는 줄어들지만, 높이는 작은쪽으로 고정이기떄문). 하지만 작은쪽을 줄이면 높이가 커질 가능성이라도 있어서 확인할 이유가 있다. 

 

높이가 같을때는 안쪽이 더 큰쪽을 해주었는데 그이유는 인덱스상의 거리는 어찌됬든 1이 줄어드는데, 높이는 최대한 그나마 높도록 유지해야 검사할 이유가 있기 때문. 

힌트를 좀 보기는 했는데, 풀어져서 신기하다. 

 

 

후기

이때까지 알고리즘 공부를 하면서 가장 어려워했던게 알고보니 투포인터 쪽이였던것같다. 내일도 이문제를 더 풀려고 한다.