# 2022 KAKAO BLIND RECRUITMENT - 파괴되지 않은 건물

- Author: @mildsalmon
- Published: 2022-02-17
- Updated: 2022-02-17
- Source: http://blex.me/@mildsalmon/2022-kakao-blind-recruitment-%ED%8C%8C%EA%B4%B4%EB%90%98%EC%A7%80-%EC%95%8A%EC%9D%80-%EA%B1%B4%EB%AC%BC
- Tags: 파이썬, 알고리즘, 프로그래머스, 코딩테스트, 문제, 누적합, imos

---

# 1. 파괴되지 않은 건물

- 난이도
	- Level 3
- 출처
	- [코딩테스트 연습 - 파괴되지 않은 건물 | 프로그래머스 (programmers.co.kr)](https://programmers.co.kr/learn/courses/30/lessons/92344)

### A. 📜 문제

위 프로그래머스 사이트에 접속하여 문제를 확인해주세요.
	
### B. 💡 내 답안

##### a. 😅 1차 시도 (실패)

```python

def check_undestroy(board):
    count = 0

    for i in range(len(board)):
        for j in range(len(board[0])):
            if board[i][j] > 0:
                count += 1

    return count


def solution(board, skill):
    for s in skill:
        t, r1, c1, r2, c2, degree = s

        for r in range(r1, r2 + 1):
            for c in range(c1, c2 + 1):
                if t == 1:
                    board[r][c] -= degree
                elif t == 2:
                    board[r][c] += degree

    return check_undestroy(board)

# 채점 결과
#
# 정확성: 53.8
# 효율성: 0.0
# 합계: 53.8 / 100.0

```

##### b. 😊 2차 시도 (성공)

```python

def solution(board, skill):
    count = 0
    imos = [[0] * (len(board[0]) + 1) for _ in range(len(board) + 1)]

    for s in skill:
        t, r1, c1, r2, c2, degree = s

        # 공격
        if t == 1:
            imos[r1][c1] -= degree
            imos[r1][c2 + 1] += degree
            imos[r2 + 1][c1] += degree
            imos[r2 + 1][c2 + 1] -= degree
        # 회복
        elif t == 2:
            imos[r1][c1] += degree
            imos[r1][c2 + 1] -= degree
            imos[r2 + 1][c1] -= degree
            imos[r2 + 1][c2 + 1] += degree

    for row in range(len(imos)):
        for column in range(1, len(imos[0])):
            imos[row][column] += imos[row][column - 1]

    for column in range(len(imos[0])):
        for row in range(1, len(imos)):
            imos[row][column] += imos[row - 1][column]

    for row in range(len(board)):
        for column in range(len(board[0])):
            board[row][column] += imos[row][column]

            if board[row][column] > 0:
                count += 1

    return count

# 채점 결과
#
# 정확성: 53.8
# 효율성: 46.2
# 합계: 100.0 / 100.0

```

##### a. 🙄 회고

> 내 풀이

- imos 알고리즘을 사용했다.
	- imos 알고리즘은 다차원 누적합이다.

> 결론

- 새로운 알고리즘 문제는 어렵다.
	- 다만, 익히면 쉬워진다.

### C. 🧐 문제 해설

> 이해한 내용을 바탕으로 작성했습니다.

![](https://static.blex.me/images/content/2022/2/17//2022_2_17_11_Bu2j6M3jW4qAteiXbBe9.jpg)

이렇게 풀면, 시간복잡도가 확 줄어든다.

1차 시도에서는 O(skill_n \* board_n^2). 즉, O(250,000 \* 1,000 \* 1,000)이고,

2차 시도에서는 O(skill_n + 2\*((board_n+1)^2) + (board_n)^2) = O(skill_n + (board_n+1)^2 + board_n^2) = O(250,000 + (1001)^2 + 1000^2) 이다.

즉, O(n\*m^2)이던 시간복잡도가 O(n+2(m^2) 정도로 줄어든 것을 알 수 있다.

# 참고문헌

2022 KAKAO BLIND RECRUITMENT. [코딩테스트 연습 - 파괴되지 않은 건물 | 프로그래머스 (programmers.co.kr)](https://programmers.co.kr/learn/courses/30/lessons/92344). Programmers. (accessed Feb 17, 2022)