[99클럽] 비기너 코딩테스트 스터디 TIL - LeetCode, 2500

 

1. 문제풀이

1) 문제, Delete Createst Value in Each Row (LeetCode, 2500)

You are given an m x n matrix grid consisting of positive integers.

Perform the following operation until grid becomes empty:

- Delete the element with the greatest value from each row. If multiple such elements exist, delete any of them.

- Add the maximum of deleted elements to the answer.

Note that the number of columns decreases by one after each operation.

Return the answer after performing the operations described above.

 

 

2) 해석

 

 

- 각 행에서 가장 큰 값을 삭제

- 삭제된 값 중 가장 큰 값을 답에 더함

 

 

3) 풀이

const handleDelete = (grid) => {
  const maxArr = [];

  for (let i = 0; i < grid.length; i++) {
    //가장 큰 값 삭제
    const max = Math.max(...grid[i]);
    const idx = grid[i].indexOf(max);

    maxArr.push(max);
    grid[i].splice(idx, 1); //grid 각 행마다 가장 큰 값 삭제
  }
  //다 돌면 그 값 중 가장 큰 값 리턴
  return Math.max(...maxArr);
};

const deleteGreatestValue = function (grid) {
  let sum = 0;
  const n = grid[0].length;

  //gird가 비어있을때까지 반복
  //답에 더하기
  for (let i = 0; i < n; i++) sum += handleDelete(grid);

  return sum;
};

 

딱히 해석할 게 없어서 문제 그대로 코드를 구현했다.

 

let sum = 0;
const n = grid[0].length;

 

우선 최종적으로 출력할 sum 변수를 만들어준다.

 

n는 grid 안의 모든 요소가 삭제될 때까지 반복문을 돌릴 때 필요한 반복 횟수이다.

각 행의 요소 개수만큼 반복해야 하기 때문에 grid[0]의 length를 n으로 지정해 줬다.

 

 

for (let i = 0; i < n; i++) sum += handleDelete(grid);

 

그리고 반복문을 만들어 준다.

handleDelete에서 각 행에서 삭제된 값의 가장 큰 수를 받아올 것이기 때문에 이를 sum에 더해준다.

 

 

const handleDelete = (grid) => {
  const maxArr = [];

  for (let i = 0; i < grid.length; i++) {
    //가장 큰 값 삭제
    const max = Math.max(...grid[i]);
    const idx = grid[i].indexOf(max);

    maxArr.push(max);
    grid[i].splice(idx, 1); //grid 각 행마다 가장 큰 값 삭제
  }
  //다 돌면 그 값 중 가장 큰 값 리턴
  return Math.max(...maxArr);
};

 

maxArr는 각 행에서 받아온 가장 큰 숫자들의 배열이다.

 

gird를 받아와 행의 수만큼 반복문을 돌려주고, 가장 큰 값을 구해서 삭제한 뒤 해당 값을 maxArr에 넣어준다.

그리고 Math.max를 이용해 삭제한 값 중 가장 큰 값을 return 해준다.

 

 

- 걸린 시간

 

 

2. 리팩토링

 

생각보다 시간이 오래 걸리는 거 같아서 다른 방법을 찾아봤다. 

 

const handleDelete = (grid) => {
    const maxArr = grid.map(row => row.pop());
    return Math.max(...maxArr)
}

const deleteGreatestValue = function(grid) {
    let sum = 0;
	
    //오름차순 정렬
    grid.forEach(row => row.sort((a, b) => a - b));

    while (grid[0].length > 0) sum += handleDelete(grid);

    return sum
};

 

 

1) 오름 차순 구현

grid.forEach(row => row.sort((a, b) => a - b));

 

 

오름차순으로 정렬한 후 반복분을 구현했다.

내림차순이 아니라 오름차순으로 구현한 이유는 가장 큰 값을 삭제해야 하기 때문이다.

 

배열의 경우 shift()를 사용해 앞 요소부터 삭제를 하게 되면, 시간 복잡도가 O(n)이 된다.

요소를 삭제한 뒤 모든 요소들을 한 칸씩 앞으로 이동시켜야 하기 때문이다.

그러나 pop을 이용해 뒤에서부터 요소를 삭제하면 다른 요소들은 이동할 필요가 없기 때문에 시간 복잡도가 O(1)이 된다.

 

가장 큰 값이 뒤에 가장 뒤에 있는 것이 좋기 때문에 정렬을 오름차순으로 구현했다. 

 

 

2) for > while로 변경

while (grid[0].length > 0) sum += handleDelete(grid);

 

for문보다 while문을 사용하는 게 더 직관적이고 깔끔할 것 같아서 while문으로 변경해 줬다.

 

 

 

3) map 사용

const maxArr = grid.map(row => row.pop());

 

기존에는 indexOf로 가장 큰 수의 인덱스 번호를 찾은 뒤, splice로 배열을 잘라줬었다.

그러나 이제는 grid가 정렬되어 있기 때문에 pop을 이용해 가장 큰 숫자를 삭제하고, 그 숫자들을 리턴 받아 maxArr에 저장해 줬다.

 

 

전 후

 

리팩토링 전과 후를 비교해 보면 확실히 후가 성능이 개선되었다!