[프로그래머스] Swift 파괴되지 않은 건물 누적합

문제 :

https://programmers.co.kr/learn/courses/30/lessons/92344

코딩테스트 연습 - 파괴되지 않은 건물

 

참고 :

https://tech.kakao.com/2022/01/14/2022-kakao-recruitment-round-1/#%EB%AC%B8%EC%A0%9C-6-%ED%8C%8C%EA%B4%B4%EB%90%98%EC%A7%80-%EC%95%8A%EC%9D%80-%EA%B1%B4%EB%AC%BC

2022 카카오 신입 공채 1차 온라인 코딩테스트 for Tech developers 문제해설

 

분석 : 

그냥 아무 생각 없이 skill -> r1 ~ r2 -> c1 ~ c2로 3중 for문으로 풀면 효율성 제로가 뜨는 것을 볼 수 있다 ㅎㅎ

도저히 해결 방법이 생각이 안나서 카카오 풀이를 참고했다 .. 

누적합을 이용해 구간합을 빠르게 구할 수 있다는 점은 알고 있었는데 2차원 배열로 보니 DFS, BFS 만 생각 날 뿐 구간합이 떠오르지 않았다. 위의 카카오 해설을 보는 것이 아주 많이 도움이 되었다 !!

구하고자 하는 2차원 구간을 3중 for문(skill, 행, 열)로 도는 것이 아니라 ==> 시간 초과

구간의 시작, 끝 값에 n만큼의 변화를 (n, -n, n, -n) 만큼 매 스킬마다 누적해준다. 그리고 각 행에 대해서 윗 행 -> 아래 행으로 누적합

각 열에 대해서 왼쪽 열 -> 오른쪽 열로 누적합 하게 되면 각 칸마다 값의 변화량이 도출된다 !!

따라서 원본 배열인 board값과 변화 값을 더해 0이상인 건물만 카운트 한다.

 

Swift 코드 :

func solution(_ board:[[Int]], _ skill:[[Int]]) -> Int {
    var cnt = 0
    var arr = Array(repeating: Array(repeating: 0, count: board[0].count + 1), count: board.count + 1)
    for i in skill {
        let type = i[0] == 2 ? true : false
        let r1 = i[1]
        let c1 = i[2]
        let r2 = i[3]
        let c2 = i[4]
        let degree = type == true ? i[5] : -i[5]

        arr[r1][c1] += degree
        arr[r2+1][c2+1] += degree
        arr[r2+1][c1] -= degree
        arr[r1][c2+1] -= degree
    }
    
    for i in 1..<arr.count { // row -> botton
        for j in 0..<arr[0].count {
            arr[i][j] += arr[i-1][j]
        }
    }
    
    for i in 1..<arr[0].count { // left -> right
        for j in 0..<arr.count{
            arr[j][i] += arr[j][i-1]
        }
    }
    
    for i in 0..<board.count { // arr(변화량) + board(초기값)
        for j in 0..<board[i].count {
            arr[i][j] += board[i][j]
            if arr[i][j] > 0 { cnt += 1 }
        }
    }
   
    return cnt
    
}

 

결과 :