시간복잡도를 줄이는 기술 3. 전처리(1) - 뒤부터 탐색하며 채우는 R배열

개념

[8, 2, 6, 7, 5, 3] 와 같이 숫자들이 주어졌을 때, 특정 위치를 적절하게 선택하여 해당 위치에 놓여있는 숫자와 그 숫자를 포함하여 뒤에 놓여있는 숫자들 중 최솟값을 곱한 값이 최대가 되도록하라. 이 경우엔 8*2 보다 7*3이 더 큼. 

기존 생각

각 위치를 한번 씩 잡아보면서 그 뒤에 있는 숫자를 전부 보며 최솟값을 구해 곱하는 식은

위치 잡는데 O(N), 뒤에 있는 숫자를 보는데 최악 O(N)이 걸리므로 총 -> :O(N^2) 시간이 걸린다. 

1. 새 아이디어 - 뒤부터 탐색하며 R배열 

R 배열 생성 : i번째부터 N번째까지 놓여있는 숫자들 중 최솟값을 저장해놓은 배열, 생성까지 O(N) 걸림

Arr[i] * R[i] 중 가장 큰 값을 구하면 되므로 총 시간 복잡도는 O(N)

• R배열은 맨 뒤부터 탐색하며, 바로 뒷 인덱스 값과 비교하여 가장 작은 값으로 채워준다.

R[n] = arr[n] 
for i in range(n - 1, 0, -1): 
	R[i] = min(R[i + 1], arr[i])

 

문제1 

문자 '(', ')'로만 이루어진 문자열 A가 주어지면 그 문자열들 사이에서 연속한 여는 괄호 두 개와 연속한 닫는 괄호 두 개로 쌍을 이룰 수 있는 서로 다른 가지수를 구하시오

입력: )((()())())

출력: 4

아이디어

• 0으로 채워진 R배열을 만든다.
• 뒤에서 부터 배열을 돌며 닫는 기호가 연속된 부분의 개수를 세준다. s[i] == s[i+1] ==’)’ 이면, R[i]= R[i+1]+1
• 아니라면, 수를 유지시켜 채운다.

예로, ))) 인 경우 → R:[2,1,0]이다,

예로, (( ))) 인 경우 → R:[2,2,2,1,0] → 앞의 ((와 쌍을 이룰 수 있는 )) 조합 수 2개

• 이제 맨 앞부터 탐색하며 (( 기호가 나왔을 때, 쌍을 이루는 가짓수를 R에서 찾아 더해줌

if s[i] == s[i+1] ==’(’ → ans+=R[i]

코드

# for i in range(len(s)-1):
#     if s[i] == s[i+1] == '(':
#         start+=1
#     elif s[i] == s[i+1] == ')':
#         close+=1
# print(start*close)

# 실패 -> 이코드의 문제 : ))(( 인 경우도 세게 된다.-> 뒤에서 부터 탐색하는 배열 필요 

#Reveres_arr, R 를 만들어 뒤부터 탐색하며 ))가 나오는 횟수를 count한다 
s= input()
n=len(s)
R = [0] * n
R[n - 1] = 0 #맨 마지막 원소는 0

for i in range(n-2,-1,-1) :
    #뒤에서부터 )) 가 있으면 만들 수 있는 조합 수 +1
    if s[i]==s[i+1]==')':
        R[i]=R[i+1]+1 
    
    #아니라면, 조합 수 그대로 
    else:
        R[i]=R[i+1]

#맨 앞부터 탐색하며 쌍을 이루는 가짓 수 R에서 찾아 더해줌 
ans = 0
for i in range(n - 2): #맨 뒤 2개는 셀 필요 X 
    if s[i] == '(' and s[i + 1] == '(':
        ans += R[i]

print(ans)