투명

1531번: 투명

 

나의 풀이

import sys

def _tutu(N, M):
    answer = 0
    tutu_dict = {}
    for _ in range(N):
        a_x, a_y, b_x, b_y = map(int, sys.stdin.readline().rstrip().split())
        for i in range(a_x, b_x + 1):
            for j in range(a_y, b_y + 1):
                if (i, j) not in tutu_dict:
                    tutu_dict[(i, j)] = 1
                else:
                    tutu_dict[(i, j)] += 1
    for v in tutu_dict.values():
        if (v > M):
            answer += 1
    return answer
        
N, M = map(int, sys.stdin.readline().rstrip().split())
print(_tutu(N, M))

 

시간 복잡도

for _ in range(N) : 좌표 범위르 순회 ( 선형 시간 복잡도 )
    for i in range(a_x, b_x + 1) : 모든 좌표를 딕셔너리 에 넣기 ( 이차형 시간 복잡도 )
        for j in range(a_y, b_y + 1):
해당 알고리즘 시간 복잡도 : 삼차형 시간 복잡도 ( O(n**3) )