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

  • 0
  • 0
0
0

1. 파괴되지 않은 건물

A. 📜 문제

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

B. 💡 내 답안

a. 😅 1차 시도 (실패)

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차 시도 (성공)

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. 🧐 문제 해설

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

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

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). Programmers. (accessed Feb 17, 2022)

이 글이 도움이 되었나요?
0 minutes ago
작성된 댓글이 없습니다. 첫 댓글을 달아보세요!
    댓글을 작성하려면 로그인이 필요합니다.