[연습문제] 확진자동선체크, 온실의크기

in 코딩테스트 on 연습문제




확진자동선체크

확진자동선체크

나의 코드

function solution(history, infected) {
  let index = history.indexOf(-infected);
  let answer = [];
  do {
    let temp = history.slice(0, index + 1);
    answer = [...answer, ...temp.filter(v => v > 0 && v !== infected)];
    let i = 0;
    while (temp.indexOf(infected) > i++) {
      if (temp[i] < 0) {
        answer.splice(answer.indexOf(-temp[i]), 1);
      }
    }

    // 반복
    history = history.slice(index + 1);
    index = history.indexOf(-infected);
  } while (index !== -1);
  return [...new Set(answer)].sort((x, y) => x - y);
}

console.log(solution([3, 2, -3, 1, -1, -2, 4, -4, 1, -1], 2));
console.log(solution([2, 4, 3, -3, 3, -2, 1, -3, -1, -4], 4));
console.log(solution([1, -1], 1));
console.log(solution([7, -7, 2, 5, 1, 4, 9, -9, -2, 3, -1, -5, 6, 10, -10, 7, -4, -6, 8, -7, 4, -3, 3, -8, -3, -4], 1));
console.log(solution([3, 1, -1, -3, 4, 1, 5, -5,-1, -4], 1));

//[ 1, 3 ]
// [ 1, 2, 3 ]
// []
// [ 2, 3, 4, 5, 9 ]
// [ 3, 4, 5 ]
  1. 확진자의 퇴장을 기준으로 배열을 자른다. (기준 배열)
  2. 확진자가 아니면서, 입장한 사람을 배열에 추가한다.
  3. 확진자 입장 전, 퇴장했던 사람을 2에서 구한 배열에서 제거한다.
  4. 확진자가 나머지 배열에 없을 때까지 1,2,3 과정을 반복한다.
  5. 최종 배열에서 set으로 중복을 없앤 후 오름차순으로 정렬한다.



온실의크기

온실의크기

나의 코드

function solution(field, n) {
  let row = field.length;
  let col = field[0].length;
  let answer = [];

  for (let i = 0; i <= col - n; i++) {
    for (let j = 0; j <= row - n; j++) {
      let cnt = 0;
      for (let k = i; k < i + n; k++) {
        for (let l = j; l < j + n; l++) {
          if (field[k][l] === 1) cnt++;
        }
      }
      answer.push(cnt);
    }
  }
  return Math.max(...answer);
}

console.log(solution([[1,0,1],[0,0,1],[0,1,1]], 2)); //3
console.log(solution([[0,0,0,1],[1,1,0,0],[0,1,0,0],[0,0,1,0]], 3)); //4
console.log(solution([[1,1,0,0,1],[0,1,1,0,0],[1,1,0,0,0],[0,0,1,1,0],[1,0,1,1,0]], 3)); //6
console.log(solution([[0]], 1)); //0
  1. 가능한 n*n 좌측상단 지점 for문 구현하기 (i, j)
  2. 해당 지점에서 우측으로 n, 아래로 n만큼 이동하며 갯수 구하기
  3. 가장 큰 cnt 출력하기


동연님 코드

function solution(field, n) {
  // field: number[][], n: number
  let answer = 0;
  let newField = Array.from(Array(field.length), () => new Array(field[0].length - n + 1));

  // 가로로 합한 값 구하기
  for (let y = 0; y < field.length; y++) {
    for (let x = 0; x <= field[y].length - n; x++) {
      newField[y][x] = field[y].slice(x, x + n).reduce((acc, curVal) => acc + curVal, 0);
    }
  }

  // 배열의 행렬을 교체
  newField = newField[0].map((col, i) => newField.map(row => row[i]));

  // 가로로 합한 값 구하기
  for (let y = 0; y < newField.length; y++) {
    for (let x = 0; x <= newField[y].length - n; x++) {
      newField[y][x] = newField[y].slice(x, x + n).reduce((acc, curVal) => acc + curVal, 0);
    }
  }

  // 최대값 구하기
  for (let i = 0; i < newField.length; i++) {
    const num = Math.max(...newField[i]);
    answer = num > answer ? num : answer;
  }
  return answer;
}

처음에 둘다 n^4 나와서 이게 최선인가 하고 포기하고 있었는데,,
동연님은,,결국,,해내셨다
n^2 으로 단축됐다!
가로를 미리 더하고, 행렬 뒤집어서 다시 가로 구하면 답이 된다는 걸 어떻게 발견하셨을까?
코드 보고도 이해하는데 한참 걸린 나…
나도 앞으로 더 좋은게 있을 거라는게 뻔하면 풀렸더라도 더 바라보고 찾아낼 수 있도록 하자!