[알고리즘/파이썬] 프로그래머스 - 파괴되지 않은 건물 (다시 풀기)

문제

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

프로그래머스

 

풀이

처음 봤을 때 뭐야 문제가..왜이렇게 쉬워...?!!!!!라면서 5분 내에 풀고 싱글벙글이었는데 아니나 다를까 정답률이 30퍼 대인 이유가 있었다. 효율성 테스트에서 멸망해버림 ㅋㅋㅋㅋ ㅠ

해시를 써야할까...? 그래도 복잡도가 O*N*M에서 벗어나기 힘들거 같은데 ... 라는 생각을 하면 삽질만 하다가 절대 내 머리로는 이 효율성을 못 뚫을 것 같아서 해설을 봤다.

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

누적합 문제였다. ㅋㅋㅋ ㅠ 아 너무 천재같은 발상이라서 할 말을 잃었지만 당시 효율성 정답률이 1퍼대여서 내가 특출나게 머리가 나쁜건 아니었구나 하고 안심했다.

 

 

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

프로그래머스

프로그래머스 질문하기 탭에서 이 분도 설명을 굉장히 잘 적어주셨다! 보고 나니 아하..그렇구나..하고 이해는 되는데 이걸 어떻게 문제를 보고 떠올릴 수 있는지... ㅠ ㅠ 난 다시 태어나도 못 그럴 것 같아서 슬프다... 이 문제는 3주 후에 다시 풀어봐야겠다!

 

코드

def solution(board, skill):
    answer = 0
    m = len(board[0])
    n = len(board)
    arr = [[0 for _ in range(m+1)] for _ in range(n+1)]

    for a in skill:
        s_type,r1,c1,r2,c2,degree = a[0],a[1],a[2],a[3],a[4],a[5]
        if s_type == 1:
            degree *= -1
        arr[r1][c1] += degree
        arr[r1][c2+1] += -1*degree
        arr[r2+1][c1] += -1 * degree
        arr[r2+1][c2+1] += degree
        
    for i in range(n):
        for j in range(m):
            arr[i+1][j] += arr[i][j]
            
    for i in range(n):
        for j in range(m):
            arr[i][j+1] += arr[i][j]
            
    for i in range(n):
        for j in range(m):
            value = arr[i][j] + board[i][j]
            if value > 0:
                answer += 1
            
    return answer