8주차 알고리즘 테스트

majungha·2023년 5월 7일
1

알고리즘

목록 보기
42/71

오늘의 알고리즘 테스트 👍

📝 1. 도미노 ( directionOfDominoes )


  • N개의 도미노가 주어집니다.

  • 각 도미노는 왼쪽으로 밀려 넘어지거나, 오른쪽으로 밀려 넘어지거나 밀리지 않은 상태로 시작합니다.

  • 만약 왼쪽으로 밀려 넘어지는 도미노가 있다면, 해당 도미노의 왼쪽에 존재하는 도미노는 함께 왼쪽으로 쓰러질 것입니다.

  • 반대의 경우인 오른쪽으로 밀려 넘어지는 도미노 역시 같은 작용을 야기합니다.

  • 예외적으로 왼쪽으로 밀려 넘어지는 도미노와 오른쪽으로 밀려 넘어지는 도미노 사이에 존재하는 도미노는 양쪽에서 영향을 받게 되어 넘어지지 않고 그대로 서있게 됩니다.

  • 문자열 dominoes를 입력 받아 위의 조건대로 쓰러진 이후의 문자열을 리턴해주세요.

    • 'R', 'L', '.' 세종류의 문자열이 조합된 dominoes가 주어집니다.
    • 오른쪽으로 밀려 넘어지는 도미노는 'R'로 표시됩니다.
    • 왼쪽으로 밀려 넘어지는 도미노는 'L'로 표시됩니다.
    • 어느쪽으로도 밀리지 않은채 시작되는 도미노는 '.'으로 표시됩니다.

▷ 입출력 예

directionOfDominoes('.L.R...LR..L..') // 'LL.RR.LLRRLL..'
directionOfDominoes('R.R.LL...LR..') // 'RRR.LLLLLLRRR'

▷ 내 풀이

function directionOfDominoes(dominoes) {
  // 여기에서 작업하세요.
  let answer = "";
  for (let i = 0; i < dominoes.length; i++) {
    if (dominoes[i] === "R") {
      answer += "R";
      if (dominoes[i + 1] === ".") {
        answer += "R";
      }
    } else if (dominoes[i] === "L") {
      answer += "L";
      if (dominoes[i - 1] === ".") {
        answer += "L";
      }
    }
  }
  return answer;
}

////////////////////////////////////////////////////////////////

function directionOfDominoes(dominoes) {
  // 여기에서 작업하세요.
  let answer = [];
  for (let i = 0; i < dominoes.length; i++) {
    if (dominoes[i] === "R") {
      answer.push("R");
      for (let j = 0; j < dominoes.length; j++) {
        if (dominoes[i + j] === ".") {
          answer.push("R");
        }
      }
    }
    if (dominoes[i] === "L") {
      answer.push("L");
      for (let j = 0; j < dominoes.length; j++) {
        if (dominoes[i + j] === ".") {
          answer.push("L");
        }
      }
    }
  }
  return answer;
}

▷ 해결 못함 ❌

  • 두가지 방법으로 접근해서 풀어보려고 했는데 시간이 부족해서 해결해지 못했다.

▷ 레퍼런스 코드

function directionOfDominoes(dominoes) {
  let forces = new Array(dominoes.length).fill(0);

  let force = 0;

  for (let i = 0; i < dominoes.length; i++) {
    // 'R'의 영향을 받는 요소 확인
    if (dominoes[i] == 'R') force = dominoes.length;
    else if (dominoes[i] == 'L') force = 0;
    else force = Math.max(force - 1, 0);
    forces[i] += force;
  }

  force = 0;
  for (let i = dominoes.length - 1; i >= 0; i--) {
    // 'L'의 영향을 받는 요소 확인
    if (dominoes[i] == 'L') force = dominoes.length;
    else if (dominoes[i] == 'R') force = 0;
    else force = Math.max(force - 1, 0);
    forces[i] -= force;
  }

  let result = '';
  // 위의 for문을 거쳐 설정된 요소들을 돌아 정수일 경우 'R', 음수일 경우 'L', 0일 경우 '.'
  for (let power of forces) result += power > 0 ? 'R' : power < 0 ? 'L' : '.';
  return result;
}

📝 2. 숫자 뽑기 ( pickNumber )


  • 정사각형 형태의 이중배열 matrix가 주어집니다.

  • matrix[i]는 숫자를 요소로 가집니다.

  • 아래의 모든 조건을 충족하는 숫자를 골라 해당 숫자만을 뽑아 담은 새로운 배열을 리턴해주세요.

    1. 뽑을 숫자는 각 행(가로)에서 가장 작은 숫자여야 합니다.
    2. 뽑을 숫자는 각 열(세로)에서 가장 큰 숫자여야 합니다.

▷ 입출력 예

pickNumber([
  [8, 7, 3],
  [9, 11, 13],
  [15, 16, 17],
]) // [15]
pickNumber([
  [1, 10, 4, 2],
  [9, 3, 8, 7],
  [15, 16, 17, 12],
]) // [12]
pickNumber([
  [1, 9, 10],
  [4, 8, 1],
  [6, 1, 7],
]) // []

▷ 내 풀이

function pickNumber(matrix) {
  // 여기에서 작업하세요.
  let answer = [];
  for (let i = 0; i < matrix.length; i++) {
    answer.push(Math.min(...matrix[i]));
  }
  console.log(Math.max(...answer), answer);
  let count = 0;
  for (let i = 0; i < answer.length; i++) {
    for (let j = i + 1; j < answer.length; j++)
      if (answer[i] === answer[j]) {
        count++;
      }
  }
  if (count > 0) {
    return [];
  }
  return [Math.max(...answer)];
}

▷ for문 사용 레퍼런스 코드

function pickNumber(matrix) {
  for (let i = 0; i < matrix.length; i++) {
    const min = Math.min(...matrix[i]);
    const idx = matrix[i].indexOf(min);

    const verify = matrix.every((arr) => arr[idx] <= min);
    if (verify) return [min];
  }
  return [];
}

▷ map, filter 매서드 사용 레퍼런스 코드

function pickNumber(matrix) {
  // 여기에서 작업하세요.
  let minInRow = matrix.map((row) => Math.min(...row));
  let maxInCol = matrix[0].map((_, i) =>
    Math.max(...matrix.map((row) => row[i]))
  );
  return minInRow.filter((smallest) => maxInCol.includes(smallest));
}

📝 3. 문자열 자르기 ( truncateString )


  • 문자열 str과 숫자 타입 데이터 limit가 주어집니다.
  • str은 각 단어들이 하나의 공백으로 구분되어 있습니다.
  • 주어진 str의 단어들을 limit만큼 자른 문자열을 리턴해 주세요.
  • str은 모두 공백과 영어 알파벳으로 이루어져 있습니다.
  • 리턴되는 문자열은 주어진 문자열과 같이 공백으로 구분 되어야 합니다.
  • 리턴되는 문자열의 끝에는 공백이 존재해서는 안됩니다.

▷ 입출력 예

truncateString('Hello World', 1) // 'Hello'
truncateString('Hello World Welcome', 2) // 'Hello World'

▷ 내 풀이

function truncateString(str, limit) {
  // 여기에서 작업하세요.
  let arrStr = str.split(" ");
  let answer = "";
  for (let i = 0; i < limit; i++) {
    if (i === limit - 1) {
      answer += arrStr[i];
    } else {
      answer += arrStr[i] + " ";
    }
  }
  return answer;
}

▷ for문 사용 레퍼런스 코드

function truncateString(str, limit) {
  // 여기에서 작업하세요.
  let answer = '';
  str = str.split(' ');

  for (let i = 0; i < limit; i++) {
    answer += str[i];
    answer += ' ';
  }

  return answer.slice(0, answer.length - 1);
}

▷ split, join 매서드 사용 레퍼런스 코드

function truncateString(str, limit) {
   return str.split(' ', limit).join(' ');
}

📝 4. 뒤죽박죽 ( topsyTurvy )


  • 문자열 str과 숫자를 요소로 가진 배열 arr이 주어집니다.
  • 문자열 str과 배열 arr은 무작위로 섞여 있습니다.
  • 배열 arr은 str을 올바르게 정렬했을 때의 각 문자 index를 요소로 가집니다.
  • 뒤섞인 문자열 str과 index를 담은 배열 arr을 입력 받아,
  • 올바르게 정렬된 문자열을 리턴해주세요.

▷ 입출력 예

topsyTurvy('crijavapts', [ 5, 6, 7, 0, 1, 2, 3, 8, 9, 4 ]) // 'javascript'
topsyTurvy('bsktcaurs', [4, 8, 7, 1, 6, 2, 5, 3, 0]) // 'starbucks'

▷ 내 풀이

function topsyTurvy(str, arr) {
  // 여기에서 작업하세요.
  let answer = "";
  let obj = {};
  for (let i = 0; i < arr.length; i++) {
    // obj = arr
    obj[arr[i]] = str[i];
  }
  // console.log(obj)

  arr.sort();
  // console.log(arr)
  for (let i = 0; i < arr.length; i++) {
    answer += obj[`${i}`];
  }
  // console.log(answer)
  return answer;
}

▷ forEach, join 매서드 사용 레퍼런스 코드

function topsyTurvy(str, arr) {
  let result = []
  arr.forEach((ele, i) => {
    result[ele] = str[i]
  })
  return result.join('')
}

출처: 코드캠프

profile
개발자 블로그 / 항상 겸손한 자세로 배우면서 성장하자 할 수 있다!

0개의 댓글