Search Insert Position

문제

Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You may assume no duplicates in the array.

정렬된 배열에서(중복된 값은 없다 가정) 타겟이 들어가야할 자리의 인덱스를 리턴해야하는 문제

Example 1:

Input: [1,3,5,6], 5
Output: 2

Example 2:

Input: [1,3,5,6], 2
Output: 1

Example 3:

Input: [1,3,5,6], 7
Output: 4

Example 4:

Input: [1,3,5,6], 0
Output: 0

풀이

나의 코드

const searchInsert = (nums, target) => {
    if ( nums.indexOf(target) !== -1 ) {
        return nums.indexOf(target);
    } else {
        if ( nums.length === 1 ) return nums[0] > target ? 0 : 1;
        if ( nums[0] > target ) return 0;
        for ( let i = 0; i < nums.length; i++ ) {
            if ( nums[i] < target && nums[i+1] > target) return i+1
        }
        return nums.length;
    }
};

문제자체가 간단하기 때문에 그냥 포문으로 돌아서 코드를 작성했는데
통과는 했지만 예외처리를 몇가지나 해야하는 부분에서 코드를 쓰면서도 맘에 안들었고, 좋은 방법이 있을 것이라 생각이 들었는데 Discuss 탭을 보니 이진 탐색(Binary Search)을 쓸 수 있는 문제였다.

이진 탐색 ( Binary Search ) 이란?

정렬된 배열에서 특정 값을 찾을 때 사용할 수 있는 알고리즘.

처음 중간의 값을 임의의 값으로 선택하여, 그 값과 찾고자 하는 값의 크고 작음을 비교하는 방식.

처음 선택한 중앙값이 만약 찾는 값보다 크면 그 값은 새로운 최고값이 되며, 작으면 그 값은 새로운 최하값이 된다. 검색 원리상 정렬된 리스트에만 사용할 수 있다는 단점이 있지만, 검색이 반복될 때마다 목표값을 찾을 확률은 두 배가 되므로 속도가 빠르다는 장점이 있다.

시간 복잡도는 O(logN)으로 빠르다.

문제를 이진탐색으로 풀면?

const searchInsert = (nums, target) => {
    let low = 0;
    let high = nums.length-1;
    while ( low <= high ) {
        let mid = parseInt((low + high)/2);
        if (nums[mid] === target) {
            return mid;
        } else if (nums[mid] > target) {
            high = mid-1;
        } else {
            low = mid+1;
        }
    }
    return low;
}

위와같이 풀리며 매우 간단


Jump Game

문제

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Determine if you are able to reach the last index.

For example:
A = [2,3,1,1,4], return true.

A = [3,2,1,0,4], return false.

0번 인덱스를 시작점으로, 각 인덱스의 값만큼 점프해서 마지막 인덱스까지 갈 수 있는지 판별하는 문제

풀이

먼저 접근한 방법은 길이가 nums와 같은 새로운 배열에 0을 할당한 뒤에,
nums와 같은 인덱스에서부터 인덱스의 값만큼 다음 인덱스에 1씩 더해주는 방법으로 생각했음.( 이해안돼도 상관X, 쓰레기같은 방법이였음.. )

const canJump = nums => {
    let arr = [];
    for ( let i = 0; i < nums.length; i++ ) {
        arr.push(0);
    }
    for ( let i = 0; i < nums.length-1; i++ ) {
        for ( let j = i+1; j <= i+nums[i]; j++ ) {
            arr[j]++;
        }
    }
    return arr.lastIndexOf(0) === 0 ? true :false;
};

하다가 말아서 정확히는 아니고 대충 위와같이 코드를 작성했고, 시간복잡도는 n^2이 나오는데 테스트케이스에 n^2으로는 통과할 수 없을 정도로 긴 케이스가 있어서, 고민하다가 검색해보니 Greedy Algorithm이라는 방법이 있어 코드를 보고 아래와 같이 작성하니 시간복잡도 n으로 통과.

const canJump = nums => {
    let lastPos = nums.length-1;
    for ( let i = nums.length-1; i >= 0; i-- ) {
        if ( i + nums[i] >= lastPos ) {
            lastPos = i;
        }
    }
    return lastPos === 0;
};

Greedy Algorithm이란 최적해를 구하는 데에 사용되는 근사적인 방법으로, 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다. 순간마다 하는 선택은 그 순간에 대해 지역적으로는 최적이지만, 그 선택들을 계속 수집하여 최종적(전역적)인 해답을 만들었다고 해서, 그것이 최적이라는 보장은 없다.

매트로이드라는 구조를 가진 문제에서는 그리디 알고리즘으로 항상 최적해를 찾을 수 있다.

위의 코드를 설명해보면

nums의 마지막 인덱스 값을 lastPos에 할당해놓고, 그 값부터 시작해서 lastPos를 0까지 도달하게 하는 것. 반복문 전체를 도는것이 아닌, 최적의 판단으로 횟수를 최대한 줄여준다.


Valid Parentheses

문제

Given a string containing just the characters ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[‘ and ‘]’, determine if the input string is valid.

The brackets must close in the correct order, “()” and “()[]{}” are all valid but “(]” and “([)]” are not.

괄호들이 개수와 순서가 맞게 적혀 있는지 판별

풀이

const isValid = s => {
    while ( s.indexOf("()") !== -1 || s.indexOf("{}") !== -1 || s.indexOf("[]") !== -1 ) {
        if ( s.indexOf("()") !== -1 ) {
            s = s.replace(s[s.indexOf("()")]+s[s.indexOf("()")+1], '')
        }
        if ( s.indexOf("{}") !== -1 ) {
            s = s.replace(s[s.indexOf("{}")]+s[s.indexOf("{}")+1], '')
        }
        if ( s.indexOf("[]") !== -1 ) {
            s = s.replace(s[s.indexOf("[]")]+s[s.indexOf("[]")+1], '')
        }
    }
    return s === '' ? true: false
};

반복문으로 쌍이 없을때까지 s의 길이를 줄여나가고, 빈문자열이 된다면 true, 아니라면 false 리턴

너무 쉬운문제만 골라서 풀고 있는 것 같다.

쉬운거 아무리 풀어봐야 소용 없으니, 내일부터 medium단계에 도전해야겠다.

Palindrome Number

문제

Determine whether an integer is a palindrome. Do this without extra space.

추가로 공간을 사용하지 않고서 팰린드롬 숫자를 판별 ( 앞뒤로 대치인 숫자 )

풀이

const isPalindrome = x => {
    if ( x < 0 ) return false; // 음수인 경우일 때 false 를 리턴
    const str = x.toString(); // 숫자를 문자로 변경
    const middle = parseInt(str.length/2); // 중간값 잡음
    for ( let i = 0; i < middle; i++ ) { // 포문으로 처음과 끝값을 비교하고 한칸씩 비교해서 모두 같으면 true 리턴
        if ( str[i] !== str[str.length-i-1] ) {
            return false;
        }
    }
    return true;
};

주석의 내용이 전부임.


Roman to Integer

문제

Given a roman numeral, convert it to an integer.

Input is guaranteed to be within the range from 1 to 3999.

로마숫자를 정수로 바꾸는 문제

풀이

const romanToInt = s => {
    const roman = {'I':1, 'V':5, 'X':10, 'L':50, 'C':100, 'D':500, 'M':1000};
    if ( s.length === 1 ) {
        return roman[s]
    }
    let result = 0;
    const special = { 'IV': 4, 'IX': 9, 'XL': 40, 'XC': 90, 'CD': 400, 'CM': 900 }
    for ( let i = 0; i < s.length-1; i++ ) {
        if ( special[s[i]+s[i+1]] ) {
            result += special[s[i]+s[i+1]];
            s = s.replace(s[i]+s[i+1], '');
            i = -1
        }
    }
    for ( let j = 0; j < s.length; j++ ) {
        result += roman[s[j]]
    }
    return result
};

문제는 어렵지 않은데 예외처리를 일일이 해줘야하는게 귀찮았음.

먼저 각각 문자가 뜻하는 숫자를 roman에 담고, 특별한 경우를 따로 special에 담는다.

우선 길이가 1개일 때 roman에서 매칭되는 값을 리턴해주고

길이가 2개 이상인 경우에는 먼저 special에 해당하는 문자가 있는지 찾아서 result에 더해준 뒤에 문자열에서 삭제해주는 포문을 하나 돌리고

남은 값들을 roman에서 매칭시켜 result에 더해주고 리턴하면 끝

객체로 묶는 생각을 바로 못해서 일일이 if문으로 했다가, 나중에 수정했음


Reverse Integer

문제

Reverse digits of an integer.

Example1: x = 123, return 321
Example2: x = -123, return -321

click to show spoilers.

Note:
The input is assumed to be a 32-bit signed integer. Your function should return 0 when the reversed integer overflows.

단순하게 숫자를 뒤집어서 출력하는 문제,

이때 32비트 정수를 넘어가면 0을 리턴

풀이

var reverse = function(x) {
    const rev = parseInt(x.toString().split('').reverse().join(''))
    if ( x > 2147483647 || rev > 2147483647 ) {
        return 0;
    } else {
        return x > 0 ? rev : -rev
    }
};

32비트 최대 정수값을 나타내는 자바스크립트 메소드가 있을줄 알고 한시간넘게 뒤졌는데 안나와서 그냥 214783647을 입력해버렸다..

설명할게 없당

3. Longest Substring Without Repeating Characters

문제

Given a string, find the length of the longest substring without repeating characters.

Examples:

Given “abcabcbb”, the answer is “abc”, which the length is 3.

Given “bbbbb”, the answer is “b”, with the length of 1.

Given “pwwkew”, the answer is “wke”, with the length of 3. Note that the answer must be a substring, “pwke” is a subsequence and not a substring.

주어진 문자열에서 중복되지 않는 가장 긴 문자열을 찾아 길이를 리턴하는 문제

풀이

const lengthOfLongestSubstring = (s) => {
    let max = 0;
    let temp = [];
    for ( let i = 0; i < s.length; i++ ) {
        temp = [];
        for ( let j = i; j < s.length; j++ ) {
            if ( temp.indexOf(s[j]) === -1 ) {
                temp.push(s[j]);
                if ( max < temp.length ) {
                    max = temp.length
                }
            } else {
                break;
            }
        }
    }
    return max
};

for문 한개로 짜보려 했는데 도무지 생각이 안나서 두개로 어떻게 짜긴 짰는데 별로 좋은 코드는 아닌것 같다.

그래도 쓰긴 쓴거니까 설명을 붙이자면,

temp라는 임시 배열에 j번째 원소가 없다면 푸시해주는 방식으로 해서 temp 배열 길이의 최대값을 max에 담아 리턴하는식

어렵다 난이도가 medium 밖에 안되는 문젠데 ㅜ 갈길이 멀다.

다른사람의 풀이

const lengthOfLongestSubstring = function(s) {
    let result = '';
    let tempResult = '';
    for ( let i = 0; i < s.length; i++ ) {
        if ( tempResult.indexOf(s[i]) == -1 ) {
            tempResult += s[i];
            if ( tempResult.length > result.length ) {
                result = tempResult;
            }
        } else {
            if ( tempResult.length > result.length ) {
                result = tempResult;
            }
            let index = tempResult.indexOf(s[i]);
            tempResult = tempResult.slice(index+1) + s[i];
        }
    }
    return result.length;
};

사실 코드를 보고도 어떻게 하는지 감이 딱 오진 않지만, 내가 짠 코드보다는 낫다는건 알 것 같다.

내공이 부족한것 같다.


Two Sum

문제

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

nums라는 배열에서 임의의 두 수의 합이 target이 될 때 그 두수의 인덱스를 리턴하는 문제.
이 때 타겟이 만들어지는 경우는 한가지밖에 없다고 가정

풀이

const twoSum = (nums, target) =>  {
    for ( let i = 0; i < nums.length; i++ ) {
        if ( nums.indexOf(target-nums[i]) !== -1 && nums.indexOf(target-nums[i]) !== i ) {
            return [i, nums.indexOf(target-nums[i])]
        }
    }
};

포문으로 첫번째 인덱스 값부터 돌 때 타겟에서 뺀값이 배열내에 존재하면 해당 인덱스를 리턴하는 식

말로 설명하는게 더어렵다 ㅜ


LeetCode 알고리즘 공부

자바스크립트로 공부하기

보시면서 틀린 부분, 이해안되는 부분, 본인이 생각하는 더 나은 코드가 있다면 남겨주시기 바랍니다!

화이팅

+ Recent posts