LeetCode 알고리즘 공부

자바스크립트로 공부하기

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

화이팅

가장 큰 정사각형 찾기 (Level 4)

문제

어떤 문장의 각 알파벳을 일정한 거리만큼 밀어서 다른 알파벳으로 바꾸는 암호화 방식을 시저 암호라고 합니다.

A를 3만큼 밀면 D가 되고 z를 1만큼 밀면 a가 됩니다. 공백은 수정하지 않습니다.

보낼 문자열 s와 얼마나 밀지 알려주는 n을 입력받아 암호문을 만드는 ceasar 함수를 완성해 보세요.

• “a B z”,4를 입력받았다면 “e F d”를 리턴합니다.

풀이

function findLargestSquare(board) {
  let max = 0;
    for ( let i = 0; i < board[0].length; i++) {
      for ( let j = 0; j < board.length; j++ ) {
        board[i][j] = board[i][j] == "O" ? 1 : 0
      }
  }
  for ( let x = 1; x < board[0].length; x++ ) {
    for ( let y = 1; y < board.length; y++ ) {
      if ( board[x][y] !=0 ) {
        board[x][y] = 1 + Math.min(board[x-1][y], board[x][y-1], board[x-1][y-1])
      }
      if ( max < board[x][y] ) {
        max = board[x][y]
      }
    }
  }
  return Math.pow(max, 2)
}

//아래 코드는 테스트를 위한 출력 코드 입니다.
var testBoard = [['X','O','O','O','X'],['X','O','O','O','O'],['X','X','O','O','O'],['X','X','O','O','O'],['X','X','X','X','X']];
console.log(findLargestSquare(testBoard));

문제보고 주변 컴공인들에게 물어보니 그냥 DP로 풀면 되네! 라고 들어서 엄청 찾아봤는데도 접근도 어려운데다가 막상 써놓고 나서도 너무 복잡하다 생각들었는데, 다른사람들 코드가 더길어서 흐뭇했다(ㅋㅋ~)

BOJ 1915번과도 동일한 문제이다.

우선 첫 번째 for문에서는 O 표시를 1 X 표시를 0으로 바꿔준다.

두 번째 for문에서는 원소가 0이 아닌것에 대해서 왼쪽,위쪽, 왼쪽위쪽 세개 값중 최솟값에 1을 더해 만들수 있는 최대 변의 길이를 적어주고, 그 값이 max보다 크다면 max에 대입하는 식으로 해서, 최대 정사각형 변의 길이를 구한 후에 제곱해 리턴!

다른 사람의 풀이

더 좋은코드가 있을수도 있겠지만, 이것보다 더 긴 코드는 읽고싶지 않다..

시저 암호 (Level 3)

문제

어떤 문장의 각 알파벳을 일정한 거리만큼 밀어서 다른 알파벳으로 바꾸는 암호화 방식을 시저 암호라고 합니다.

A를 3만큼 밀면 D가 되고 z를 1만큼 밀면 a가 됩니다. 공백은 수정하지 않습니다.

보낼 문자열 s와 얼마나 밀지 알려주는 n을 입력받아 암호문을 만드는 ceasar 함수를 완성해 보세요.

• “a B z”,4를 입력받았다면 “e F d”를 리턴합니다.

풀이

function caesar(s, n) {
  let arr = [];
  n = n % 26
  for ( let i = 0; i < s.length; i++ ) {
    const word = s.charCodeAt(i)
      if ( word == 32 ) {
      arr.push(" ")
    }
    else if ( word >= 65  && word <= 90 ) {
        if ( word+n > 90 ) {
          arr.push(String.fromCharCode(word+n-26))
      } else {
        arr.push(String.fromCharCode(word+n))
      }
    }
    else if ( word >= 90 && word <= 122 ) {
        if ( word+n > 122 ) {
          arr.push(String.fromCharCode(word+n-26))
      } else {
          arr.push(String.fromCharCode(word+n))
      }
    }
  }
  return arr.join("")
}

// 실행을 위한 테스트코드입니다.
console.log(caesar("abcdef", 25));

좀 오래걸린듯하다. 배열로 처리했음

다른 사람의 풀이

function caesar(s, n) {
    var result = "";
    // 함수를 완성하세요.
  var car = ""
  for (var i=0; i<s.length;i++)
  {        
    if ( s[i] == ' ' )
      result += ' '
    else 
        result += String.fromCharCode( (s.charCodeAt(i)>90)?
      (s.charCodeAt(i)+n-97)%26+97 : (s.charCodeAt(i)+n-65)%26+65 )     
  }
    return result;
}
// 실행을 위한 테스트코드입니다.
console.log('s는 "a B z", n은 4인 경우: ' + caesar("a B z", 4));

원리는 비슷하나 문자열로 조금더 간결한 코드

야근지수 (Level 3)

문제

야근 지수

회사원인 수민이는 많은 일이 쌓여 있습니다.

수민이는 야근을 최소화하기 위해 남은 일의 작업량을 숫자로 메기고, 일에 대한 야근 지수를 줄이기로 결정했습니다.

야근 지수는 남은 일의 작업량을 제곱하여 더한 값을 의미합니다.

수민이는 1시간 동안 남은 일 중 하나를 골라 작업량 1만큼 처리할 수 있습니다.

수민이의 퇴근까지 남은 N 시간과 각 일에 대한 작업량이 있을 때, noOvertime 함수를 제작하여 수민이의 야근 지수를 최소화 한 결과를 출력해 주세요.

예를 들어, N=4 일 때, 남은 일의 작업량이 [4, 3, 3] 이라면 야근 지수를 최소화하기 위해 일을 한 결과는 [2, 2, 2]가 되고 야근 지수는 22 + 22 + 22 = 12가 되어 12를 반환해 줍니다.

풀이

function noOvertime(no, works) {
  let arr =works.replace(/\[/,'').replace(/\]/,'').split(",")
  for ( let i = 0; i < arr.length; i++ ) {
      arr[i] = +arr[i]
  }
  for ( let j = 0; j < no; j++ ) {
      arr.sort((a,b) => { return b-a });
    arr[0] = arr[0] - 1
  }
    return arr.map((x) => { return x*x }).reduce((a,b) => { return a+b})
}
console.log(noOvertime(4,"[4,3,3]"))

function noOvertime(no, works) {
  let k = 0;
  let arr =works.replace(/\[/,'').replace(/\]/,'').split(",")
  for ( let i = 0; i < arr.length; i++ ) {
      arr[i] = +arr[i]
  }
  arr.sort((a,b) => { return b-a });
   while ( k < no ) {
    for ( let j = 0; j < arr.length-1; j++ ) {
        if ( arr[j] > arr[j+1] ) {
          k += arr[j]-arr[j+1]
        let l = arr[j] - arr[j+1]
        arr[j] = arr[j] - l
      }
    }
    return arr.map((x) => { return x*x }).reduce((a,b) => { return a+b})
  }
}

console.log(noOvertime(4,"[4,3,3]"))

내가 잘모르는건지 애초에 문제가 이상한건지..

완전 하드스트레스

다른 사람의 풀이

통과못함

N개의 최소공배수 (Level 3)

문제

두 수의 최소공배수(Least Common Multiple)란 입력된 두 수의 배수 중 공통이 되는 가장 작은 숫자를 의미합니다.

예를 들어 2와 7의 최소공배수는 14가 됩니다.

정의를 확장해서, n개의 수의 최소공배수는 n 개의 수들의 배수 중 공통이 되는 가장 작은 숫자가 됩니다.

nlcm 함수를 통해 n개의 숫자가 입력되었을 때, 최소공배수를 반환해 주세요.

예를들어 [2,6,8,14] 가 입력된다면 168을 반환해 주면 됩니다.

풀이

function nlcm(num) {
    let res = [num[0]];
  for ( let i = 1; i < num.length; i++ ) {
    let max = 1;
    for ( let j = 2; j <= Math.min(res[i-1], num[i]); j++ ) {
          if (( res[i-1] % j == 0 ) && ( num[i] % j == 0 )) {
        if ( max < j ) { max = j } 
        }
    }
    res[i] = res[i-1]*num[i]/max
  }
  return res[res.length-1]
}

// 아래는 테스트로 출력해 보기 위한 코드입니다.
console.log(nlcm([2,6,8,14]));

꽤 오래 걸린 것 같음.. 생각하고서 쓰질않고 쓰고나서 생각해버리니까 아예 방향을 잘못잡아서 고생함.

res라는 배열에 num배열에서 순차적으로 두 수의 최대공배수를 계산해 삽입.

res[0] = num[0]

res[0],num[1] => res[1]

res[1],num[2] => res[2]

…

res[num.length-2],num[num.length-1] => 결과

이런식으로 계산을 했다.

썩 마음에 드는 코드는 아닌 것 같다.

다른 사람의 풀이

function nlcm(num) {
  return num.sort((a, b) => a - b).reduce(lcm);
}
function lcm(num1, num2){
  return (num1 * num2) / gcd(num1, num2);
}
function gcd(num1, num2){
  if(num2 == 0) return num1;
  return gcd(num2, num1%num2);
}

// 아래는 테스트로 출력해 보기 위한 코드입니다.
console.log(nlcm([2,6,8,14]));

이런식으로 풀어보려 했는데, 머리가 너무 복잡해져서 떠올리지 못해버렸다..

으렵다

멀리 뛰기 (Level 3)

문제

효진이는 멀리 뛰기를 연습하고 있습니다. 효진이는 한번에 1칸, 또는 2칸을 뛸 수 있습니다. 칸이 총 4개 있을 때, 효진이는

(1칸, 1칸, 1칸, 1칸)

(1칸, 2칸, 1칸)

(1칸, 1칸, 2칸)

(2칸, 1칸, 1칸)

(2칸, 2칸)

의 5가지 방법으로 맨 끝 칸에 도달할 수 있습니다.

멀리뛰기에 사용될 칸의 수 n이 주어질 때, 효진이가 끝에 도달하는 방법이 몇 가지인지 출력하는 jumpCase 함수를 완성하세요.

예를 들어 4가 입력된다면, 5를 반환해 주면 됩니다.

풀이

function jumpCase(num) {
    let arr = [1,2];
  for ( let i = 2; i < num; i++ ) {
    arr.push(arr[i-1]+arr[i-2])
  }
  return arr[arr.length-1]
}

//아래는 테스트로 출력해 보기 위한 코드입니다.
console.log(jumpCase(4));

내용을 잘 보면 피보나치 수열이란걸 알 수 있고, 재귀함수 대신에 반복문으로 풀어봄.

아마 이게더 빠르지 않나 싶은데 확실히는 모르겠당

다른 사람의 풀이

function jumpCase(num) {
    if (num === 1) return 1
  if (num === 2) return 2
  return jumpCase(num-1) + jumpCase(num-2)
}

재귀함수로 푸는 방법!

다음 큰 숫자 (Level 3)

문제

어떤 수 N(1≤N≤1,000,000) 이 주어졌을 때, N의 다음 큰 숫자는 다음과 같습니다.

• N의 다음 큰 숫자는 N을 2진수로 바꾸었을 때의 1의 개수와 같은 개수로 이루어진 수입니다.
• 1번째 조건을 만족하는 숫자들 중 N보다 큰 수 중에서 가장 작은 숫자를 찾아야 합니다.

예를 들어, 78을 2진수로 바꾸면 1001110 이며, 78의 다음 큰 숫자는 83으로 2진수는 1010011 입니다.

N이 주어질 때, N의 다음 큰 숫자를 찾는 nextBigNumber 함수를 완성하세요.

풀이

function nextBigNumber(n){
  let result = 0;
    for ( let i = n+1; ; i++) {
      if ( n.toString(2).match(/1/gi).length == i.toString(2) .match(/1/gi).length) {
        return i
    }
  }
}

//아래 코드는 테스트를 위한 코드입니다.
console.log(nextBigNumber(78));

이진법으로 변경후에 1의 개수를 비교해 같은 결과가 나올때까지 반복 후 i 리턴

다른 사람의 풀이

가독성은 다른 코드들이 괜찮지만, 짧은코드가 더 좋아서(고수느낌ㅎ) 안가져왔음

콜라츠 추측 (Level 2)

문제

1937년 Collatz란 사람에 의해 제기된 이 추측은, 입력된 수가 짝수라면 2로 나누고, 홀수라면 3을 곱하고 1을 더한 다음, 결과로 나온 수에 같은 작업을 1이 될 때까지 반복할 경우 모든 수가 1이 된다는 추측입니다.

예를 들어, 입력된 수가 6이라면 6→3→10→5→16→8→4→2→1 이 되어 총 8번 만에 1이 됩니다.

collatz 함수를 만들어 입력된 수가 몇 번 만에 1이 되는지 반환해 주세요.

단, 500번을 반복해도 1이 되지 않는다면 –1을 반환해 주세요.

풀이

function collatz(num) {
  let count = 0;
    while ( num > 1 ) {
    if ( count >= 500 ) {
      return -1
    } else {
      if ( num % 2 == 0 ) {
        num = num /2
      } else {
        num = num*3 + 1
      }
      count++
    }
  }
  return count
}

// 아래는 테스트로 출력해 보기 위한 코드입니다.
console.log( collatz(6) );

그냥 보이는 그대로 코드짠거라 어렵지는 않고 딱히 부연설명도 필요 없는듯 하다.

다른 사람의 풀이

function collatz(num) {
    var answer = 1;
    while((num = doCalc(num)) != 1){
    answer++;
    if(answer == 500) return -1;
  }
    return answer;
}
function doCalc(num){
  return num % 2 == 0 ? num / 2 : (3 * num) + 1;
}

// 아래는 테스트로 출력해 보기 위한 코드입니다.
console.log( collatz(6) );

비슷한데 함수를 두개로 쪼개서 호출하는 방법.

이게 더 괜찮은 듯 하다.