Cavity Map

https://www.hackerrank.com/challenges/cavity-map/problem?isFullScreen=true

Cavity Map | HackerRank

 

나의 코드

#!/bin/python3

import math
import os
import random
import re
import sys
import copy

def cavityMap(grid):
    answer = []
    maps = [list(i) for i in grid]
    cp_maps = copy.deepcopy(maps)
    for i in range(1, len(grid)-1):
        for j in range(1, len(grid[0])-1):
            ck = True
            for m_x, m_y in ((-1,0), (1,0), (0,-1), (0,1)):
                new_x, new_y = i+m_x, j+m_y
                if maps[new_x][new_y] >= maps[i][j]:
                    ck = False
                    break
            if ck:
                cp_maps[i][j] = 'X'
    for i in cp_maps:
        answer.append(''.join(i))

    return answer
    
if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')
    n = int(input().strip())
    grid = []
    for _ in range(n):
        grid_item = input()
        grid.append(grid_item)
    result = cavityMap(grid)
    fptr.write('\n'.join(result))
    fptr.write('\n')
    fptr.close()

 

시간 복잡도

maps = [list(i) for i in grid] : maps 만들기 ( 이차형 시간 복잡도 )

cp_maps = copy.deepcopy(maps) : 깊은 복사 ( 이차형 시간 복잡도 )

    for i in range(1, len(grid)-1) : 모든 maps을 순회 ( 이차형 시간 복잡도 )
        for j in range(1, len(grid[0])-1):

for i in cp_maps : 최종 maps을 문자열로 변환해 삽입 ( 이차형 시간 복잡도 )
        answer.append(''.join(i))

해당 알고리즘 시간복잡도는 이차형 시간 복잡도 ( O(n**2) )