[Leetcode] 20. Valid Parentheses , 69. Sqrt(x), 66. Plus One

20. Valid Parentheses

링크

https://leetcode.com/problems/valid-parentheses/description/

 

 

풀이

시간 - 26:00

function checkParent(char) {
    if (char === '(') return 's'
    if (char === ')') return 'sc'
    if (char === '{') return 'm'
    if (char === '}') return 'mc'
    if (char === '[') return 'l'
    if (char === ']') return 'lc'
}

var isValid = function(s) {
    let stack = []
    for (let i =0; i<s.length; i+=1) {
        const parentChar = checkParent(s[i])

        if (stack.length){
            const lastEle = stack[stack.length-1]
            if ((lastEle + 'c') === parentChar) {
                stack.pop()
            } else if(lastEle === parentChar) {
                stack.push(parentChar)
            } else if (parentChar[parentChar.length-1] === 'c') {return false} 
            else {
                stack.push(parentChar)
            }
        }else {
            if (parentChar[parentChar.length-1] === 'c') return false
            stack.push(parentChar)
        }
    }

    if (stack.length) return false
    return true
};

# 리팩토리 코드
var isValid = function(s) {
    const stack = [];
    const pairs = { ')': '(', '}': '{', ']': '[' };

    for (const char of s) {
        if (char in pairs) { // 닫는 괄호인지 확인
            if (!stack.length || stack.pop() !== pairs[char]) return false;
        } else {
            stack.push(char); // 여는 괄호는 스택에 추가
        }
    }

    return stack.length === 0; // 모든 괄호가 짝을 이루면 true
};

인사이트

1. 반복, 조건문을 더 깔끔하게 쓸 수 있을 거 같음

2. pair일 때는 hashMap이 꽤 유용한 거 같음

 

 

---

69. Sqrt(x)

 

링크

https://leetcode.com/problems/sqrtx/submissions/

 

 

풀이

시간 - 22:29

var mySqrt = function(x) {
    // 자릿 수를 구한다.
    let digit = x.toString().length %2 === 1 ? (x.toString().length-1)/2 : x.toString().length/2
    if (x === 0) return 0
    // x2를 해가면서 범위를 찾는다.
    if (digit === 0) digit = 1
    let smallX = Number('1' + '0'.repeat(digit-1))
    let largeX = smallX
    while (largeX <= x/2){
        largeX *= 2
    }
    // 범위를 찾았다면, 거기서 이분 탐색을 진행한다.
    while (smallX < largeX){
        const mid = Math.floor((smallX +largeX)/2)
        if (mid *mid === x) return mid
        if (smallX ===mid || largeX === mid) break

        if (mid*mid <x) {smallX = mid}
        else {largeX = mid}
    }

    // 가장 가까운 정수를 비교하면서 찾는다.
    if ((x-smallX*smallX) <= (x-largeX * largeX)) {
        return smallX
    }
    return largeX-1
};

 

인사이트

1. 이분탐색 자체가 log(N)이다보니, 가지치기가 횟수를 그리 안 줄일 수도 있다. 즉, 시간복잡도 상에서 그리 큰 이득을 얻지 못할 수도 있다.

 

 

---

66. Plus One

 

링크

https://leetcode.com/problems/sqrtx/submissions/

 

 

풀이

시간 - 13:17

var plusOne = function(digits) {
    let addOne = false
    for (let i=digits.length-1; i >=0; i-=1){
        const caculatedNum = digits[i] + 1
        digits[i] = caculatedNum % 10
        
        if (digits[i] !== 0) {
            break
        } else if(i === 0){
            addOne = true
        }
    }

    if (addOne) {digits.unshift(1)}

    return digits
};

# 리팩토링
var plusOne = function(digits) {
    for (let i=digits.length-1; i >=0; i-=1){
        digits[i] = (digits[i] + 1) % 10
        if (digits[i] !== 0) {
            return digits
        }
    }

    digits.unshift(1)
    return digits
};

인사이트

1. 최대 정수 범위를 고려 못했다.

2. 뭔가 코드를 복잡하게 짜는 느낌이 좀 있다. 설계가 명확하지 않아서 그런 듯 (리팩토링 전후)