가장 긴 팰린드롬 ( Level 2, JavaScript )

문제

앞뒤를 뒤집어도 똑같은 문자열을 palindrome이라고 합니다.
longest_palindrom함수는 문자열 s를 매개변수로 입력받습니다.
s의 부분문자열중 가장 긴 palindrom의 길이를 리턴하는 함수를 완성하세요.
예를들어 s가 토마토맛토마토이면 7을 리턴하고 토마토맛있어이면 3을 리턴합니다.

풀이

function longest_palindrom(s){
  let res = 1, j
  for ( let i = 1; i < s.length - 1; i++ ) {
    j = 1;
    while ( i >= j && i+j <= s.length && s[i+j] === s[i-j] ) {
      j++
    }
    if ( j*2 -1 > res ) res = j*2 - 1
  }
  return res
}

문자열에서 앞뒤로 하나하나 비교하면서 최대길이의 팰린드롬을 찾는 방법

안좋은코드지만 별다른 방법이 생각나지 않았음

다른 사람의 풀이

function longest_palindrom(s){
  if (s === s.split("").reverse().join("")) {
    return s.length;
  } else {
    var A = longest_palindrom(s.substring(0, s.length-1));
    var B = longest_palindrom(s.substring(1, s.length));
    return Math.max(A, B);
  }
}

재귀로 풀었는데 개모싯다

2 x n 타일링 ( Level 5, JavaScript )

문제

1x1 정사각형 2개가 붙어 있는 타일이 있습니다. 이 타일을 이용하여 총 2xN 의 보드판을 채우려고 합니다. 타일은 가로, 세로 두 가지 방향으로 배치할 수 있습니다.

보드판의 길이 N이 주어질 때, 2xN을 타일로 채울 수 있는 경우의 수를 반환하는 tiling 함수를 완성하세요.

단, 리턴하는 숫자가 매우 커질 수도 있으므로 숫자가 5자리를 넘어간다면 맨 끝자리 5자리만 리턴하세요.예를 들어 N = 2일 경우 가로로 배치하는 경우와 세로로 배치하는 경우가 있을 수 있으므로 2를 반환해 주면 됩니다. 하지만 만약 답이 123456789라면 56789만 반환해주면 됩니다. 리턴하는 숫자의 앞자리가 0일 경우 0을 제외한 숫자를 리턴하세요. 리턴타입은 정수형이어야 합니다.

풀이

function tiling(n) {
    let arr = [1, 2];
  for ( let i = 2; i < n; i++ ) {
      arr[i] = arr[i-1] + arr[i-2];
    if ( arr[i].toString().length > 5 ) {
        arr[i] = Number(arr[i].toString().slice(-5));
    }
  }
  return Number(arr[n-1].toString().slice(-5));
}

피보나치 수열로 이해하면 되는데 이때 5자리 이상의 숫자들을 slice(-5)로 잘라주면서 배열에 넣어야 n이 커졌을 때도 연산이 가능하다

다른 사람의 풀이

똑같음

slice(-5) 대신 %10000 을 써놓은 분도 있었음

최고의 집합 ( Level 4, JavaScript )

문제

자연수 N개로 이루어진 집합 중에, 각 원소의 합이 S가 되는 수의 집합은 여러 가지가 존재합니다. 최고의 집합은, 위의 조건을 만족하는 집합 중 각 원소의 곱이 최대가 되는 집합을 의미합니다. 집합 원소의 개수 n과 원소들의 합 s가 주어지면, 최고의 집합을 찾아 원소를 오름차순으로 반환해주는 bestSet 함수를 만들어 보세요. 만약 조건을 만족하는 집합이 없을 때는 배열 맨 앞에 –1을 담아 반환하면 됩니다. 예를 들어 n=3, s=13이면 [4,4,5]가 반환됩니다.
(자바는 집합이 없는 경우 크기가 1인 배열에 -1을 담아 반환해주세요.)

풀이

function bestSet(n, s) {
  if ( n > s ) return [-1];
    const ave = parseInt(s/n);
  let result = new Array(n).fill(ave);
  for ( let i = 0; i < s-n*ave; i++ ) {
      result[result.length-1-i] += 1
  }
  return result
}

if문으로 예외처리를 해준 뒤

s를 n으로 나눈 몫을 n개 원소에 채워 넣은 뒤에, 남은 수를 차례대로 1씩 더해 리턴

다른 사람의 풀이

똑같음

숫자의 표현 ( Level 4, JavaScript )

문제

수학을 공부하던 민지는 재미있는 사실을 발견하였습니다. 그 사실은 바로 연속된 자연수의 합으로 어떤 숫자를 표현하는 방법이 여러 가지라는 것입니다. 예를 들어, 15를 표현하는 방법은
(1+2+3+4+5)
(4+5+6)
(7+8)
(15)
로 총 4가지가 존재합니다. 숫자를 입력받아 연속된 수로 표현하는 방법을 반환하는 expressions 함수를 만들어 민지를 도와주세요. 예를 들어 15가 입력된다면 4를 반환해 주면 됩니다.

풀이

function expressions(num) {
  let result = 0, sum = 0, j;
    for ( let i = 1; i <= num; i++ ) {
    sum = 0, j = i;
      while ( sum <= num ) {
      sum += j;
      if ( sum === num ) result++;
      j++
    }
  }
  return result;
}

이중포문으로 sum과 num이 같을 때 결과값에 1씩 더해서 결과값을 리턴

다른 사람의 풀이

function expressions(num) {
    var answer = 0;

  for(var i=1; i<=num; i++) {
    if (num%i == 0 && i%2 == 1)
      answer++
  }
    return answer;
}

신박하네 어떻게 접근한건지..

머리가 안돌아가니까 나중에 조금더 고민해봐야겠다.

야근 지수 ( Level 3, JavaScript )

문제

야근 지수
회사원인 수민이는 많은 일이 쌓여 있습니다. 수민이는 야근을 최소화하기 위해 남은 일의 작업량을 숫자로 메기고, 일에 대한 야근 지수를 줄이기로 결정했습니다. 야근 지수는 남은 일의 작업량을 제곱하여 더한 값을 의미합니다. 수민이는 1시간 동안 남은 일 중 하나를 골라 작업량 1만큼 처리할 수 있습니다. 수민이의 퇴근까지 남은 N 시간과 각 일에 대한 작업량이 있을 때, noOvertime 함수를 제작하여 수민이의 야근 지수를 최소화 한 결과를 출력해 주세요. 예를 들어, N=4 일 때, 남은 일의 작업량이 [4, 3, 3] 이라면 야근 지수를 최소화하기 위해 일을 한 결과는 [2, 2, 2]가 되고 야근 지수는 22 + 22 + 22 = 12가 되어 12를 반환해 줍니다.

풀이

function noOvertime(no, works) {
    while ( no > 0 ) {
      works = works.sort((a,b) => { return b-a });
    works[0] -= 1;
    no--;
  }
  return works.map( a => { return a*a }).reduce((a,b) => { return a+b });
}

오랜만에 다시 본 못풀었던 문젠데 다시 풀긴 풀었는데, 마땅히 좋은 풀이가 떠오르지는 않는다.

계속해서 sort를 반복하기 때문에 썩 좋은 코드는 아닌듯하다.

다른 사람의 풀이

적을만한 더 좋은 풀이가 안보인다

가장 큰 정사각형 찾기 (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]"))

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

완전 하드스트레스

다른 사람의 풀이

통과못함