[Programmers] 바탕화면 정리 - 161990

for 문 하나를 써도 index() 연산으로 시간 복잡도는 O(n*m)로 이중 for문과 같다. 

 

Question

 

머쓱이의 컴퓨터 바탕화면의 상태를 나타내는 문자열 배열 wallpaper가 매개변수로 주어질 때 바탕화면의 파일들을 한 번에 삭제하기 위해 최소한의 이동거리를 갖는 드래그의 시작점과 끝점을 담은 정수 배열을 return하는 solution 함수를 작성해 주세요. 드래그의 시작점이 (lux, luy), 끝점이 (rdx, rdy)라면 정수 배열 [lux, luy, rdx, rdy]를 return하면 됩니다.

 

 

Code 1 : 이중 for 문

• Time Complexity : O(n*m)

def solution(wallpaper):
    x = []
    y = []
    
    for idxY,i in enumerate(wallpaper):
        for idxX,j in enumerate(i):
            if j=='#':
                x.append(idxX)
                y.append(idxY)
    
    return [min(y), min(x), max(y)+1, max(x)+1]

 

Code 2 : My code

• Time Complexity : O(n*m)
  • for 문 : O(n)
  • i.index('#') : O(m) m은 문자열의 최대 길이.

def solution(wallpaper):
	lux,luy, rdx,rdy = -1,-1,-1,-1
        
    for idx,i in enumerate(wallpaper): # 시작 지점 찾기.
        if lux == -1 and '#' in i : 
            lux = idx
            luy = i.index('#')
        elif '#' in i :
            if i.index('#') < luy : luy = i.index('#')
        
        if '#' in i and i.rindex('#') > rdy : rdy = i.rindex('#') # 끝 지점 한 곳 찾기.
        
    for idx,i in enumerate(wallpaper[::-1]):
        if '#' in i :
            rdx = len(wallpaper)-idx
            break
    
    return [lux, luy, rdx, rdy+1]

 

now me

On my github