Portfolio

문제

풀이

현석


function solution(board, skill) {
    const columnLength = board.length
    const rowLength = board[0].length
    
    const rowCreator = () => new Array(rowLength +1).fill(0)
    const imosBoard = new Array(columnLength + 1)
        .fill(null)
        .map(rowCreator)
  
    skill.forEach(([type, r1, c1, r2, c2, degree]) => {
        const increment = type === 2 ? degree : -degree
        
        imosBoard[r1][c1] += increment
        imosBoard[r1][c2 + 1] -= increment
        imosBoard[r2 + 1][c1] -= increment
        imosBoard[r2+ 1][c2+ 1] += increment
    })
    for (let i = 0; i < columnLength; i++) {
        for (let j = 0; j < rowLength; j++) {
            imosBoard[i][j + 1] += imosBoard[i][j]  
        }
    }
    
    for (let j = 0; j < rowLength; j++) {
        for (let i = 0; i < columnLength; i++) {
            imosBoard[i + 1][j] += imosBoard[i][j]  
        }
    }
    
    let count = 0
    
    for (let j = 0; j< rowLength; j++) {
        for (let i = 0; i< columnLength; i++) {
            count += (imosBoard[i][j] + board[i][j] > 0) ? 1 : 0
        }
    }
    
    return count
}

효성

cache 사용하면 효율성 통과할 거라 생각했는데 꼭 imos로 풀어야 했군요!?

실패한 풀이 (시간 초과)


function solution(board, skill) {
    const n = board.length;
    const m = board[0].length;
    
    let answer = n * m;
    let cacheBoard = Array.from(Array(n), () => Array(m).fill(false));
    
    skill.forEach(s => {
        const [type, r1, c1, r2, c2, degree] = s;

        for(let i = r1; i <= r2; i++) {
            for(let j = c1; j <= c2; j++) {
                if(type === 1) {
                    board[i][j] -= degree; 
                }
                else {
                    board[i][j] += degree; 
                }
                
                if(board[i][j] <= 0 && !cacheBoard[i][j]) {
                    answer--;
                    cacheBoard[i][j] = true;
                }
                else if(board[i][j] > 0 && cacheBoard[i][j]) {
                    answer++;
                    cacheBoard[i][j] = false;
                }
            }
        }
    });

    return answer;
}

imos를 사용한 풀이


function solution(board, skill) {
    const n = board.length;
    const m = board[0].length;
    let answer = 0;
    let imos = Array.from(Array(n + 1), () => Array(m + 1).fill(0));
    
    skill.forEach(s => {
        const [type, r1, c1, r2, c2, degree] = s;
        
        imos[r1][c1] += (type === 1 ? -degree : degree);
        imos[r1][c2 + 1] += (type === 1 ? degree : -degree);
        imos[r2 + 1][c1] += (type === 1 ? degree : -degree);
        imos[r2 + 1][c2 + 1] += (type === 1 ? -degree : degree);
    });
    
    for(let i = 0; i < n; i++) {
        let sum = 0;
        for(let j = 0; j < m; j++) {
            sum += imos[i][j];
            imos[i][j] = sum;
        }
    }
    
    for(let i = 0; i < m; i++) {
        let sum = 0;
        for(let j = 0; j < n; j++) {
            sum += imos[j][i];
            imos[j][i] = sum;
        }
    }
    
    for(let i = 0; i < n; i++) {
        for(let j = 0; j < m; j++) {
            board[i][j] += imos[i][j];
            
            if(board[i][j] > 0) {
                answer += 1;
            }
        }
    }

    return answer;
}

재영


const solution = (board, skill) => {
  let answer = 0;

  const rowLength = board.length;
  const colLength = board[0].length;

  const arr = Array.from({ length: rowLength + 1 }, () =>
    new Array(colLength + 1).fill(0)
  );

  skill.forEach((s) => {
    const [type, r1, c1, r2, c2, degree] = s;

    const start = type === 1 ? -1 * degree : degree;
    const end = -1 * start;

    arr[r1][c1] += start;
    arr[r1][c2 + 1] += end;

    arr[r2 + 1][c1] += end;
    arr[r2 + 1][c2 + 1] += start;
  });

  for (let i = 0; i < rowLength; i += 1) {
    for (let j = 1; j < colLength + 1; j += 1) {
      arr[i][j] += arr[i][j - 1];
    }
  }

  for (let col = 0; col < colLength; col += 1) {
    for (let row = 1; row < rowLength + 1; row += 1) {
      arr[row][col] += arr[row - 1][col];
    }
  }

  for (let i = 0; i < rowLength; i += 1) {
    for (let j = 0; j < colLength; j += 1) {
      if (arr[i][j] + board[i][j] > 0) answer += 1;
    }
  }

  return answer;
};

파괴되지 않은 건물

문제

풀이