[코딩테스트] 🌇 파괴되지 않은 건물 - Kakao 2022

문제링크

문제링크

난이도

레벨 3

유형

구현, 구간합, 누적합

소요시간

1시간 못품, 카카오 풀이 참고

회고

첫 풀이에서 정확성 테스트는 통과했으나, 효율성 테스트는 떨어졌다. 연산을 하지 않고, 누적해놨다가, 한 번에 반영을 하는 방향으로 고민을 해봤다. 하지만 그래도 여전히 전체 배열을 순회하기에 시간복잡도를 줄이기에는 부족했다. JPEG 압축처럼 연산을 줄여보려고 고민했지만 결국 시간이 너무 지나서 카카오 풀이를 보고 문제를 풀었다.

 

질문 게시판에 사고 과정을 나타낸 글이 있었는데, 앞으로 이런식으로 사고를 해보면 좋을 것 같다.

https://school.programmers.co.kr/questions/30876

프로그래머스

구간합, 누적합에 대한 풀이가 잘 나와있는 포스트

https://twd0622.tistory.com/109

[알고리즘] 누적합 (Prefix Sum)

 

코드

import Foundation

func solution(_ board:[[Int]], _ skill:[[Int]]) -> Int {
    var board = board
    var prefixSum = Array(repeating: Array(repeating: 0, count: board[0].count + 1), count: board.count + 1)
    
    func acc(_ skill: [Int]) {
        let (type, sr, sc, er, ec, degree) = (skill[0], skill[1], skill[2], skill[3], skill[4], skill[5])
        prefixSum[sr][sc] += degree * (type == 1 ? -1 : 1)
        prefixSum[sr][ec + 1] -= degree * (type == 1 ? -1 : 1)
        prefixSum[er + 1][sc] -= degree * (type == 1 ? -1 : 1)
        prefixSum[er + 1][ec + 1] += degree * (type == 1 ? -1 : 1)
    }
    
    for round in (0..<skill.count) {
        acc(skill[round])
    }
    
    // 누적합 가로
    for i in (0..<board.count) {
        for j in (1..<board[0].count) {
            prefixSum[i][j] += prefixSum[i][j - 1]
        }
    }
    
    // 누적합 세로
    for j in (0..<board[0].count) {
        for i in (1..<board.count) {
            prefixSum[i][j] += prefixSum[i - 1][j]
        }
    }
    
    var answer = 0
    
    for i in (0..<board.count) {
        for j in (0..<board[0].count) {
            if board[i][j] + prefixSum[i][j] > 0 {
                answer += 1
            }
        }
    }
    return answer
}

 

https://tech.kakao.com/posts/488

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