Knowledge Map

2차원 배열의 체크 알고리즘 문제 본문

알고리즘

2차원 배열의 체크 알고리즘 문제

2017. 9. 13. 13:29

https://www.codewars.com/kata/two-arrays-zero-rows-and-zero-columns


자세한 문제 및 테스트는 위의 주소에 가서 하면 된다.


문제 자체는 단순하다. 2개의 2차원 배열을 주고 그 배열의 합의 결과로 나오는 배열에서 내부 값이 전부 0인 행과 열의 갯수을 구하면 된다.


처음에는 별생각 없이 2개의 배열의 합으로 나오는 배열을 하나 만든 다음에 거기서 0을 체크하는 방식으로 했다. 그렇게 만들어서 테스트를 했더니... 너무 느린 코드라고 피드백이 왔다. 그래서 체크 항목을 거의 없다 시피해서 했는데도 느리다고 나왔다. 결국 두 배열의 합으로 만들어지는 배열과 관련된 로직이 느리다는 이야기였다.


두 배열의 합으로 만들어지는 배열 생성로직을 삭제하고, 두 배열의 합과 그 결과값을 비교하는 로직을 바로 만들었다. for 루프가 가장 빠르므로 이것으로 순회를 했다. 그렇게 각각 행과 열을 비교하는 로직을 짰더니 통과가 되었다.


하지만 곰곰히 생각해 보니 2번이나 순회할 필요 없이 1번 전부 순회할때 각 열의 값을 캐쉬하면 되겠다는 생각이 들어서 다시 수정해서 짜보았다. 


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
function countZeroRowsAndColumns(arr1,arr2){
  var all = true;
  var result = 0;
  
  var l = arr1.length;
  var c = arr1[0].length;
  var temp = 0;
  
  // 각 열의 합을 캐쉬할 배열 생성
  var checkCol = "0".repeat(c).split("").map(o=>+o);
  
  // 행을 체크
  for(var i = 0; i < l; i++) {
    for(var j = 0; j < c; j++){
      if((temp = arr1[i][j]+arr2[i][j]) !== 0) all = false;
 
      // 각 열의 값을 캐쉬한다.
      checkCol[j] += temp;
    }
    if(all) result += 1;
    all = true;
  }
 
  // 캐쉬 했던 각 열의 합을 체크한다.
  for(var i = 0; i < c; i++){ if(checkCol[i] === 0) result += 1;}
 
  return result;
}
cs


'알고리즘' 카테고리의 다른 글

HackerRank - Between Two Sets  (0) 2017.10.22
달팽이  (0) 2017.09.24
테스트 문제 (1)  (2) 2017.09.06
각 자릿수 합  (0) 2017.09.01
정렬이란?  (0) 2016.09.21
Comments