TIL - 알고리즘 : 타워 레이저

문제

• [6,9,5,7,4] 와 같이 타워 높이가 value로 들어가는 리스트가 주어지고, 각 타워에서 왼쪽으로(0번 인덱스 방향으로) 레이저를 쏜다.
• 레이저는 레이저를 쏜 타워보다 높은 타워가 맞는다. 레이저를 쏜 타워의 인덱스 위치에 레이저를 맞은 타워의 번째(인덱스 + 1)를 넣는다.
• 가장 높은 타워는 왼쪽으로 레이저를 쏴도 레이저가 맞지 않기 때문에 결과 값의 위치에 0이 들어간다.
• 인덱스가 0인 타워는 왼쪽에 아무 것도 없기 때문에 결과 값의 위치에 0이 들어간다.
• input : [6,9,5,7,4]
• output : [0,0,2,2,4]

수정 전

def get_sign(towers):
   n = len(towers)
   
    # 결과값이 들어갈 리스트
    result = []
    
    # 마지막 인덱스부터 0번째 인덱스 까지 역순으로 for문을 돌린다.
    for i in range(n-1, -1, -1):
    	
        # i 값의 이전 인덱스부터 다시 for문을 돌린다. 왼쪽에 있는 타워의 크기확인 위해서
        for j in range(i-1, -1, -1):
        
        	# 기준이 되는 타워(i)보다 비교대상 타워(j)가 작을때 + for문이 돌고 마지막 인덱스 까지 왔을 때 결과값에 0을 추가해줌.
            if (towers[i] > towers[j]) and j == 0:
                result.append(0)
                
            # 기준이되는 타워(i)보다 비교대상 타워(j)가 크면 레이저가 멈추기 때문에 결과값에 j를 추가해줌(번째이기 때문에 +1해준다). 그리고 break를 걸어서 그 다음 타워에 영향이 안가도록함.
            elif  towers[i] < towers[j]:
                result.append(j+1)
                break
        
        # 제일 처음 인덱스는 왼쪽에 타워가 없기 때문에 0을 넣어줌.
        if i == 0:
            result.append(0)
    
    # 역순으로 체크했기 때문에 reverse로 결과값을 반전시켜줌.
    result.reverse()
    return result

수정 후

def get_sign(towers):
    n = len(towers)
    
    # 결과값을 처음부터 길이가 n이고 value가 0인 리스트로 만들어줌.
    result = [0] * n
    
    # 역순으로 체크
    for i in range(n-1, -1, -1):
        
        # 비교 기준 타워(i)와 비교 대상 타워(j)를 배교하기 위해 역순으로 for문 돌려줌.
        for j in range(i-1, -1, -1):
            
            # 비교기준타워가 비교대상타워보다 작으면 결과값의 해당 인덱스에 값을 j+1로 치환해주고 break를 걸어줌.
            if  towers[i] < towers[j]:
                result[i] = j+1
                break
        
    return result