[프로그래머스] 파괴되지 않은 건물(파이썬)-카카오 인턴쉽 기출

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

프로그래머스

문제풀다가

헛웃음을 나오게 한 문제.

 

처음에 이 문제가 lv3이라해서 긴장했는데

읽다보니 상당히 쉬웠습니다.

문제에 있는거 그냥 구현만 하면 되네.

뭐야 개꽁인데?

효율성??뭐 얼추 맞겠지 뭐.

테케 다 통과 오케.

효용성...다 시간초과??

 

아니. 이걸 어떻게 시간을 줄여?

고토 와타시가 뭘 잘못했지?

이걸 어떻게 시간을 줄이지?

 

하고 질문하기를 보니...

누적합이라는 걸 쓰지 않으면

시간이 절대로 해결안되는 문제였습니다.

덕분에 누적합에 대한 개념도 공부하게 되었던 문제.

https://tech.kakao.com/2022/01/14/2022-kakao-recruitment-round-1/

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

문제 6에 누적합에 대한 설명과 함께

자세하게 왜 써야하는지 나와있습니다.

 

좀 더 쉽게 말하자면

누적합을 쓰면

기존에 skill갯수xNxM을 했던 걸

skill갯수+NxM만 해줘도 됩니다.

왜냐면 일일이 탐색하는 방식을 쓰지 않아도 되니까요.

0으로 된 새로운 배열에 누적합을 해주고

그걸 기존 배열에 더해주면 끝.

def solution(board, skill):
    answer = 0
    b_h=len(board)
    b_w=len(board[0])
    new_board=[[0]*(b_w+1) for _ in range(b_h+1)]
    for now_skill in skill:
        sx,sy=now_skill[1],now_skill[2]
        ex,ey=now_skill[3],now_skill[4]
        degree=now_skill[5]
        #공격
        if now_skill[0] == 1:
            new_board[sx][sy]-=degree
            new_board[ex+1][sy]+=degree
            new_board[sx][ey+1]+=degree
            new_board[ex+1][ey+1]-=degree
        #회복

        elif now_skill[0]==2:
            new_board[sx][sy]+=degree
            new_board[ex+1][sy]-=degree
            new_board[sx][ey+1]-=degree
            new_board[ex+1][ey+1]+=degree




    #누적합 실시
    #왼-->오
    for x in range(b_h+1):
        for y in range(1,b_w+1):
           new_board[x][y]=new_board[x][y-1]+new_board[x][y]

    #위 아래
    for y in range(b_w+1):
        for x in range(1,b_h+1):
            new_board[x][y]=new_board[x-1][y]+new_board[x][y]


    for x in range(b_h):
        for y in range(b_w):
            board[x][y]+=new_board[x][y]
            if board[x][y]>0:
                answer+=1

    return answer

 

카카오 문제는 진짜.

이게 뭐지?싶은 문제들이 있네요.

덕분에 누적합에 대해서 충격요법으로 깨닫고 갑니다.