Softeer 연습문제(2단계) - 나무 공격

Candidate | Softeer Assessment UI

Candidate | Softeer Assessment UI

 

나의 풀이

import sys

def _attack(first_start, first_end, b):
    attack_count = 0
    for i in range(first_start, first_end + 1):
        for j in range(b):
            if map_list[i][j]:
                attack_count += 1
                map_list[i][j] = 0
                break
    return attack_count

def _main(first_start, first_end, second_start, second_end, p_count):
    p_count -= _attack(first_start, first_end, b)
    p_count -= _attack(second_start, second_end, b)
    return p_count

a, b = map(int, sys.stdin.readline().rstrip().split())
map_list, p_count = [], 0
for _ in range(a):
    now_list = list(map(int, sys.stdin.readline().rstrip().split()))
    map_list.append(now_list)
    p_count += now_list.count(1)

first_start, first_end = map(int, sys.stdin.readline().rstrip().split())
second_start, second_end = map(int, sys.stdin.readline().rstrip().split())
print(_main(first_start - 1, first_end - 1, second_start - 1, second_end - 1, p_count))

 

시간 복잡도

for _ in range(a) : a 크기만큼 순회 ( 선형 시간 복잡도 )
	~~~
    p_count += now_list.count(1) : 1의 갯수를 카운트 ( 선형 시간 복잡도 )
해당 알고리즘 시간 복잡도 : 이차형 시간 복잡도 ( O( n**2 ) )