Py) 프로그래머스 92344 파괴되지 않은 건물

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

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

 

1차 시도: 40분

2차 시도: 

 

0. 입출력

 

1. 김예고리즘

1-1. 접근 및 로직

1) skill의 원소에서 시작지점과 끝지점을 구한 뒤 해당 부분을 for문에 넣어서 board의 원소 값을 계산해준다.

 

1-2. 내 코드 -> 효율성 탈락

def solution(board, skill):
    answer = 0

    for skills in skill:
        start = (skills[1], skills[2])
        end = (skills[3], skills[4])
        point = skills[5]

        if skills[0] == 1:      # 공격
            for a in range(start[0], end[0]+1):
                for b in range(start[1], end[1]+1):
                    board[a][b] -= point

        if skills[0] == 2:      # 방어
            for a in range(start[0], end[0]+1):
                for b in range(start[1], end[1]+1):
                    board[a][b] += point

    for i in board:
        for j in i:
            if j > 0:
                answer += 1

    return answer

 

 

2. Solution

2-1. 사용 알고리즘: imos법

 

2-1. 로직

1) 각 사각형이 시작하고 끝나는 부분에 가중치를 기록한다.

2) 가중치끼리 계산하고 이후 board와 더해서 실제 값을 구함

 

2-2. 코드

def solution(board, skill):
    answer = 0
    # 시작점, 끝점, 가중치를 입력해둘 배열
    imos = [[0] * (len(board[0]) + 1) for _ in range(len(board) + 1)]

    for row in skill:
        # 명령 쿼리에 따라 imos 배열에 4개의 꼭짓점에 각각 해당하는 값을 지정한다.
        if row[0] == 1:
            imos[row[1]][row[2]] += -row[5]
            imos[row[3] + 1][row[2]] += row[5]
            imos[row[1]][row[4] + 1] += row[5]
            imos[row[3] + 1][row[4] + 1] += -row[5]
        else:
            imos[row[1]][row[2]] += row[5]
            imos[row[3] + 1][row[2]] += -row[5]
            imos[row[1]][row[4] + 1] += -row[5]
            imos[row[3] + 1][row[4] + 1] += row[5]

    # imos 배열을 가로, 세로로 훑으면서 입력해둔 값을 통해 진짜 값을 계산
    # 가로
    for i in range(len(imos)):
        now = 0
        for j in range(len(imos[0])):
            now += imos[i][j]
            imos[i][j] = now
    # 세로
    for i in range(len(imos[0])):
        now = 0
        for j in range(len(imos)):
            now += imos[j][i]
            imos[j][i] = now

    # 마지막으로 board 배열과 합치면서 0보다 큰 값의 개수를 구한다.
    for i in range(len(board)):
        for j in range(len(board[0])):
            board[i][j] += imos[i][j]
            if board[i][j] > 0:
                answer += 1

    return answer

 

3. 새롭게 알게 된 것

imos 법  ref - https://velog.io/@nkrang/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-imos-%EB%B2%95

효율성을 지키면서 누적합 문제를 풀 수 있음

1) 시작점과 끝점에 가중치를 적어줌. 

2) 누적된 가중치로 최종적인 가중치 계산

3) 가중치 계산 후 실제 값에 더해줌

* 끝점에 가중치의 음수값을 넣어주는 이유는 가중치를 더해서 쭉 끝점까지 왔을 때 0이 돼서 해당 가중치가 나머지 값에 더이상 유효하게 작용하지 않도록 하기 위함임