[programmers] 알고리즘 문제 해설 | protect-me

🕊 링크

알고리즘 문제 해설
https://programmers.co.kr/learn/courses/18

자릿수 더하기

최종 코드

function solution(n) {
  let sum = 0;
  while (n > 0) {
    sum += n % 10;
    n = Math.floor(n / 10)
  }
  return sum
}

1차 코드(정확성 테스트 21 실패)

function solution(n) {
  return (n + '').split("").reduce((acc, cur) => +acc + +cur)
}

순열 검사

최종 코드

function solution(arr) {
  const l = arr.length
  const max = Math.max(...arr)
  return l === max ? true : false
}

1차 코드(효율성 테스트 전체 실패)

function solution(arr) {
  const l = arr.length
  for (let i = 1; i <= l; i++) {
    if (!arr.includes(i))
      return false
  }
  return true
}

2차 코드(정확성 테스트 4,10 | 효율성 테스트 전체 실패)

function solution(arr) {
  arr.sort()
  const l = arr.length
  for (let i = 0; i < l; i++) {
    if (arr[i] !== i + 1) return false
  }
  return true
}

나머지 한 점

1차 코드(성공)

function solution(v) {
  const x = []
  const y = []
  v.forEach(item => {
    const [a, b] = item
    x.push(a)
    y.push(b)
  })

  const xx = deleteDup(x)
  const yy = deleteDup(y)
  return [...xx, ...yy]
}


function deleteDup(arr) {
  for (let i = 0; i < arr.length; i++) {
    for (let j = 0; j < arr.length; j++) {
      if (i !== j && arr[i] == arr[j]) {
        arr.splice(i, 1)
        arr.splice(j - 1, 1)
      }
    }
  }
  return arr
}

2차 코드(성공)

function solution(v) {
  const x = []
  const y = []
  v.forEach(item => {
    const [a, b] = item
    x.push(a)
    y.push(b)
  })

  const xx = deleteDup(x)
  const yy = deleteDup(y)
  console.log(xx, yy);
  // return [...xx, ...yy]
}

function deleteDup(arr) {
  const q = {}
  arr.forEach(item => {
    q[String(item)] = (q[String(item)] + 1 || 1);
  })
  for (let key in q) {
    if (q[key] == 1) return key
  }
}

가장 큰 정사각형 찾기 | 동적 프로그래밍 | DP

최종 코드

참고

function solution(board)
{
    let result = 0;
    let resultArr = board.slice();
    //board의 현재값이 1일경우 왼쪽상단 ,위쪽  ,왼쪽 값중에 가장 작은 값..
    for(let i=0;i<board.length;i++){
        for(let j=0;j<board[i].length;j++){
            if(board[i][j] ===1){
                if(i-1 < 0 || j-1 <0 ){
                    resultArr[i][j] = board[i][j];
                    result = Math.max(resultArr[i][j], result);
                    continue;
                }
                resultArr[i][j] = Math.min(board[i-1][j], board[i][j-1], board[i-1][j-1]) + board[i][j];
                result = Math.max(resultArr[i][j], result);
            }
        }   
    }
    return Math.pow(result,2)
}

1차 코드(추가 테스트케이스 실패)

참고
한 줄이면서, 모든 값이 0일 경우 ex) [[0,0,0,0]]
=> 기대값 0, 결과값 1 (실패)

function solution(arr) {
  const x = arr.length
  const y = arr[0].length
  let answer = 0;
  if (x == 1 || y == 1) return 1

  for (let i = 1; i < x; i++) {
    for (let j = 1; j < y; j++) {
      if (arr[i][j] > 0) {
        arr[i][j] = Math.min(arr[i - 1][j], arr[i][j - 1], arr[i - 1][j - 1]) + 1
      }
      answer = answer < arr[i][j] ? arr[i][j] : answer
    }
  }
  return Math.pow(answer, 2)
}

땅따먹기

function solution(arr) {
  let l = arr.length
  for (let i = 1; i < l; i++) {
    for (let j = 0; j < 4; j++) {
      const pastArr = []
      arr[i - 1].forEach((item, index) => {
        if (index !== j) pastArr.push(item)
      })
      const pastMax = Math.max(...pastArr)
      arr[i][j] += pastMax
    }
  }
  return Math.max(...arr[l - 1])
}