21-03-21 알고리즘 문제풀기 및 노트 정리

가장 큰 정사각형 찾기

1과 0으로 채워진 표가 있고 1로 이루어진 정사각형 중 가장 큰 정사각형의 넓이를 리턴하는 문제

DP를 사용해 풀어야 한다

function solution (board) {
    let lengthY = board.length;
    let lengthX = board[0].length;
    let max = 0;
    if(lengthX < 2 || lengthY <2) {
        return 1;
    }

    for(let i = 1; i < lengthY; i++) {
        for(var j=1; j< lengthX; j++) {
            if(board[i][j] > 0) {
                board[i][j] = Math.min(
                    board[i-1][j-1], // 좌상단
                    board[i][j-1],   // 왼쪽
                    board[i-1][j])   // 오른쪽
                    + 1              // 현재값
            } 

            if(max < board[i][j]){
                max = board[i][j]
            }
        }
    }
    return Math.pow(max, 2)
}

다음 큰 숫자

해당 문제 링크

1
2
3

조건 1. n의 다음 큰 숫자는 n보다 큰 자연수 입니다.
조건 2. n의 다음 큰 숫자와 n은 2진수로 변환했을 때 1의 갯수가 같습니다.
조건 3. n의 다음 큰 숫자는 조건 1, 2를 만족하는 수 중 가장 작은 수 입니다.

내 풀이

function solution (n) {
    let largeNumber = n; // 나중에 리턴할 값
    let binary = n.toString(2).split(''); // n을 2진수로 바꾸고
    let cntOne = binary.filter(num => parseInt(num,10) > 0).length; // 1의 갯수를 filter하여 카운트
    
    while(true) {
        largeNumber++; // 값을 증가시키고
        let lnBinary = largeNumber.toString(2).split('') // 같은 방법으로 2진수로 변환하고
        let cntThisOne = lnBinary.filter(num => parseInt(num, 10) > 0).length; // 1의 갯수를 같은 방법으로 카운트
        if (cntThisOne === cntOne) // 만약에 n의 이진수가 갖는 1의 개수가 원래 값의 1의 개수랑 같다면 빠져나가기
            break;
    }
    return largeNumber;
}

시프트 연산자를 사용한 해법

function nextBigNumber(n) {
    var i, j;
    for (i = 0; !(n & 1); i++) {
        n = n >> 1; 
        } // 1을 찾을때까지 우로 쉬프트, 쉬프트 횟수 = i
    for (j = 0; n & 1; i++, j++) {
        n = n >> 1; 
        } // 0을 찾을때까지 우로 쉬프트, 1의 갯수 = j
    for (j--, n++; i !== j; i--) {
        n = n << 1; 
        } // 0자리에 1대입, 1의 갯수 -1, i === j 가 될때까지 죄로 쉬프트하면서 쉬프트 횟수 -1
    for (i; i; i--, n++) {
        n = n << 1; 
        } // i === 0 될때까지 좌로 쉬프트 하면서 쉬프트 횟수 -1, 0자리에 1대입
    return n;
}

올바른 괄호

해당 문제 링크

function solution(s){
    let stack = [];
    let split = s.split('')

    if (split[0] === ')') return false;

    console.log(split);
    console.log(stack);

    while(split.length > 0) {
        // 만약에 split[0]이 '(' 괄호라면 split에서 빼서 stack에 넣음
        if (split[0] === '(')
            stack.push(split.shift()); 
        // 만약에 split[0]이 ')'이고
        else {
            // stack에 '('가 있다면
            if (stack.includes('(')){
                stack.pop(); // 마지막으로 넣은 괄호를 빼고
                split.shift(); // split내에서도 하나 빼기
                console.log("stack", stack)
                console.log("split", split)
            } else {
                return false;
            }
        }
    }
    
    return stack.length > 0 ? false : true;
}

이 풀이는 효율성 테스트를 통과하지 못함
while문을 사용한 것이 문제였을까?

필터를 사용해보기로 했다

let split = s.split('')
   if (split[0] === ')') return false;
   let countLeft = split.filter(branket => branket === '(').length;
   let countRight = split.filter(branket => branket === ')').length;

   return countLeft === countRight ? true : false;

테스트 케이스를 통과하지 않는 경우가 있어 실패…

else if 케이스를 만들어서 가능한 수를 하나 더 고려해야 했음

function solution2_1(s) {
    let answer = true; 
    let left = 0; 
    let split = s.split('');

    for(let item of split) {
        if (item === '(') { // 왼쪽 괄호를 찾으면 left를 더해준다
            left++
        } else if (left > 0) { // 만약 '('가 아니라면 ')'일 것이고 그렇다면 left를 줄여준다
            left--
        } else { // 이 둘 다 아니라면 괄호의 짝이 없다는 뜻
            return false;
        }
    }

    answer = left === 0 ? true : false; // left가 0이 아니라면 false 일 것
    return answer;
}

21-03-21 알고리즘 문제풀기 및 노트 정리

가장 큰 정사각형 찾기

다음 큰 숫자

올바른 괄호

Harry Kim