Knowledge Map

HackerRank - 3D Surface Area 본문

알고리즘

HackerRank - 3D Surface Area

2017. 11. 17. 13:16

문제 

3d-surface-area-English.pdf

1 X 1 사이즈의 블럭을 보드를 보고 쌓는다. 보드는 H X W 이며 H는 높이, W는 너비이다.

// 예를 들어 3X3 보드가 있다면 아래와 같이 한다.

1 3 4
2 2 3
1 2 4

보드위에 적힌 숫자를 보고 그만큼의 블럭을 쌓는 것이다.

1 X 1 X 1 일 경우에 표면적은 면적 1짜리가 6면이므로 6이다. 각각의 블럭들은 1 X 1 블럭으로 할 경우 좌표 (i, j) 로 나타낼수 있다. 각 블록은 Aij로 나타낼 수 있다. 좀더 자세한 문제내용은 위의 pdf를 참고하면 된다.

조건

  • 1 <= H, W <= 100
  • 1 <= Aij <= 100
  • i,j는 모두 정수이다.

예시

/************ 입력 *************/
1 1
1
/* 실제 입력은
첫번쨰
[1,1]
두번째
[[1]] <=실제 처리해야할 대상
*/


/************ 출력 *************/
6
/************ 입력 *************/
3 3
1 3 4
2 2 3
1 2 4

/* 
실제 입력은
첫번째
[3,3]
두번째 
[[1,3,4],
 [2,2,4],
 [1,2,4]]
*/

/************ 출력 *************/
60


풀이

처음에 문제 접근을 잘못해서 아무리 풀어도 잘못된 답이 나왔었다. 그래서 Discussions 가서 보니까 내가 문제를 완전히 다르게 보고있었다는 것을 알게 되었다. 그다음에 중간에 0이 나온다거나 골짜기일 경우를 생각해야 한다는 팁과 테스트 케이스 2개 정도를 보고나서 다시 로직을 변경해서 짜보니 다행히 잘 나왔다.


먼저 정육면체를 예로 들어보자

윗면와 아랫면, 왼쪽 면과 오른쪽 면, 앞면과 뒷면이 있다. 이렇게 3부분으로 나누어서 각각을 구하는 로직을 짠다음에 그 결과값을 result에 넣었다. 만약 2개 이상의 배열이 들어올경우 옆 블록과 겹치는 면이 왼쪽면 또는 오른쪽 면에서 발생을 하게 된다. 그럴 경우에는 겹치는 면을 이전 배열(contactArr) 과 비교한 다음에 작은 값을 기준으로 값을 가져온다음 위의 result에서 값을 빼주었다.



처음 풀었던 코드



function surfaceArea(A) {
  var contactArr = Array(A[0].length).fill(0);
  var result = 0;
  A.forEach(one => {
    let temp = 0;
    result += one.filter( o=> o > 0).length *2;
    result += one.reduce( (p,a) => p+a) * 2;
 
    one.reduce( (p,a) => {temp += Math.abs(p-a); return a;},0);
    temp += one[one.length-1];
        
    result += temp;
    result -= one.reduce( (p,a,i) => p + Math.min(a, contactArr[i]), 0* 2;
    contactArr = one.slice();
  });
  return result;
}

cs




다시 고친 코드

코드에 보면 foreach안에 filter, reduce가 총 4개나 된다. 하지만 잘생각해보면 이렇게 까지 할 필요가 없기 때문에 forEach 안에서  for문 하나로 다 처리할수 있도록 로직을 살짝 변경해 보았다.



function surfaceArea(A) {
  var contactArr = Array(A[0].length).fill(0);
  var result = 0;
  A.forEach(one => {
    let [upDownArea, sideArea, contactArea] = [000];
    let frontBackArea = one[one.length-1];
 
    for(let i = 0; i < one.length; i++) {
      if(one[i] > 0) upDownArea++;
      sideArea += one[i];
      frontBackArea += Math.abs(one[i] - (one[i-1]||0));
      contactArea += Math.min(one[i], contactArr[i]);
    }
    
    // frontBackArea는 다 구하기 때문에 x2 할 필요가 없다.
    result += (upDownArea + sideArea - contactArea)*2 + frontBackArea;
    contactArr = one.slice();
  });
  return result;
}

cs


Comments