[코딩테스트] 프로그래머스 문제모음

1. 안전지대

프로그래머스

폭탄 주변이 중복될수 있으니 중복제거를 위해 객체로 접근했다.

 

(1) 1번 풀이

function solution(board) {
  const boomIndex = {};
  for (let i = 0; i < board.length; i++) {
    for (let k = 0; k < board.length; k++) {
      if (board[i][k] == 1) {
        boomIndex[i - 1 + "" + (k - 1)] = 1;
        boomIndex[i - 1 + "" + k] = 1;
        boomIndex[i - 1 + "" + (k + 1)] = 1;
        boomIndex[i + "" + (k - 1)] = 1;
        boomIndex[i + "" + k] = 1;
        boomIndex[i + "" + (k + 1)] = 1;
        boomIndex[i + 1 + "" + (k - 1)] = 1;
        boomIndex[i + 1 + "" + k] = 1;
        boomIndex[i + 1 + "" + (k + 1)] = 1;
      }
    }
  }
  return (
    board.length ** 2 -
    Object.keys(boomIndex).filter(
      (v) => v[0] < board.length && v[1] < board.length
    ).length
  );
}

테스트케이스 7만 실패 => 2자리수의 행렬인 board가 나오면 오류

 

(2) 2번 풀이

function solution(board) {
  let boomIndex = {};
  for (let i = 0; i < board.length; i++) {
    for (let k = 0; k < board.length; k++) {
      if (board[i][k]) {
        if (i + 1 < board.length && k + 1 < board.length)
          boomIndex[i + 1 + "" + (k + 1)] = 1;
        if (k + 1 < board.length) {
          boomIndex[i - 1 + "" + (k + 1)] = 1;
          boomIndex[i + "" + (k + 1)] = 1;
        }
        if (i + 1 < board.length) {
          boomIndex[i + 1 + "" + (k - 1)] = 1;
          boomIndex[i + 1 + "" + k] = 1;
        }
        boomIndex[i - 1 + "" + (k - 1)] = 1;
        boomIndex[i - 1 + "" + k] = 1;
        boomIndex[i + "" + (k - 1)] = 1;
        boomIndex[i + "" + k] = 1;
      }
    }
  }
  const boom = Object.keys(boomIndex).filter((v) => +v >= 0).length;
  return board.length ** 2 - boom;
}

조건을 for문안에 다 넣어버렸다.

2. 짝지어 제거하기

프로그래머스

스택큐라는 알고리즘을 알게된 문제

(1) 1번 풀이

function solution(s) {
  for (let i = s.length - 1; i > 0; i--) {
    if (s[i] == s[i - 1]) {
      s = s.split(s[i] + s[i - 1]).join("");
    }
    if (s == "") return 1;
  }
  return 0;
}

효율성테스트 시간초과

for문안에 배열메서드들을 사용해서 시간복잡도가 O(n^2)

 

(2) 스택큐 풀이

function solution(s) {
  const arr = [];
  for (const value of s) {
    if (value == arr.at(-1)) arr.pop();
    else arr.push(value);
  }
  return arr.length ? 0 : 1;
}

 

배열 메서드들중 push와 pop은 시간복잡도가 O(1)이다.

그래서 두 메서드들을 이용해 배열을 이용해 스택을 만들었다.

3. n개의 최소 공배수

프로그래머스

예전 알게된 유클리드 호재법을 복습하는 느낌이다.

function solution(arr) {
  return arr.reduce((a, b) => {
    [a, b] = a > b ? [a, b] : [b, a];
    let r;
    for (var ab = a * b; (r = a % b); a = b, b = r) {}
    return (a = ab / b);
  });
}

4. 삼총사

프로그래머스

function solution(number) {
  let answer = 0;
  for (let i = 0; i < number.length - 2; i++) {
    for (let k = i + 1; k < number.length - 1; k++) {
      for (let j = k + 1; j < number.length; j++) {
        if (number[i] + number[k] + number[j] == 0) answer += 1;
      }
    }
  }
  return answer;
}

5. 숫자짝궁

프로그래머스

 

(1) 1번 풀이

function solution(X, Y) {
  var answer = [];
  for (let i = 0; i < X.length; i++) {
    if (Y.includes(X[i])) {
      answer.push(X[i]);
      Y = Y.replace(X[i], "");
    }
  }
  return answer.length == 0 ? "-1" : answer.sort((a, b) => b - a).join("") + "";
}

런타임 오류 

for문안에 replace, includes 가 들어가서 시간복잡도가 O(n^2)이다.

 

(2) 2번풀이

function solution(X, Y) {
  //X 요소들 배열에 넣기
  const obj1 = {};
  for (let i = 0; i < X.length; i++) {
    obj1[X[i]] ? (obj1[X[i]] += 1) : (obj1[X[i]] = 1);
  }
  //요소들 비교해서 있으면 temp배열에 채우기
  const temparr = [];
  for (let j = 0; j < Y.length; j++) {
    if (obj1[Y[j]]) {
      obj1[Y[j]] -= 1;
      temparr.push(Y[j]);
    }
  }
  const answer = temparr.sort((a, b) => b - a).join("");
  return answer[0] == 0 ? "0" : answer ? answer : "-1";
}

시간복잡도 O(n)을 만들기 위해 객체 이용

6. 콜라 문제

프로그래머스

function solution(a, b, n) {
  var answer = 0;
  let maxGiv = 0;
  while (a <= n) {
    maxGiv = ~~(n / a);
    answer += maxGiv * b;
    n = n - maxGiv * (a - b);
  }
  return answer;
}