[BaekJoon] 15926 현욱은 괄호왕이야!! (Gold 3) - Python

문제

 

여는 괄호 ‘(’와 닫는 괄호 ‘)’로 구성된 문자열에서 아래의 조건을 만족하는 문자열을 올바른 괄호 문자열이라고 부른다.

1. () 는 올바른 괄호 문자열이다
2. 어떤 문자열 x가 올바른 괄호 문자열이라면, (x)도 올바른 괄호 문자열이다.
3. 어떤 문자열 x와 y가 올바른 괄호 문자열이라면, xy도 올바른 괄호 문자열이다.

현욱은 친구로부터 생일 선물로 굉장히 긴 괄호 문자열을 받았다(도대체 왜 이런 걸 선물하는걸까?). 하지만 현욱은 올바른 괄호 문자열이 아니면 굉장히 싫어하기 때문에, 받은 괄호 문자열에서 연속한 일부분을 잘라서 올바른 괄호 문자열을 만들려고 한다. 그리고 이왕이면 긴 문자열이 좋으니 현욱은 부분 구간을 최대한 길게 잘라내려고 한다. 현욱을 도와 주어진 괄호 문자열에서 위의 조건을 만족하는 가장 긴 부분 문자열의 길이를 계산하는 프로그램을 작성해보자.

---

입출력 예시

 

입력: 첫 줄에 문자열의 길이 n (1 ≤ n ≤ 200,000)이 주어진다.

둘째 줄에 괄호로만 구성된 길이 n짜리 문자열이 주어진다.

출력: 주어진 문자열에서 길이가 가장 길면서 올바른 괄호 문자열인 부분 문자열의 길이를 출력한다. 올바른 괄호 문자열인 부분 문자열을 찾을 수 없는 경우 0을 출력한다.

 

입력예시1)

5
(())(

출력예시1)

4

 

입력예시2)

14
(()))()((()))(

출력예시2)

8

---

코드

 

import sys
input = sys.stdin.readline # 입력 빠르게

N = int(input())
S = list(input().rstrip()) # 괄호 입력
stack = [] # 스택 생성
cnt = [0 for _ in range(N)] # 카운트 리스트 생성

# 아래 과정을 통해 카운트 리스트에 쌍을 갖는 괄호의 인덱스를 찾아 1로 변경한다.
for i in range(N): # N만큼 반복
    if S[i] == '(': stack.append(i) # 만약 S[i]가 여는 괄호라면, 해당 인덱스 값을 스택에 추가
    else: # 만약 S[i]가 닫는 괄호라면
        if stack: # 스택이 비어있지 않다면
            cnt[i] = 1 # 현재 인덱스의 카운트 값을 1로 설정
            cnt[stack[-1]] = 1 # 스택의 맨 위에 있는 인덱스의 카운트 값을 1로 설정
            stack.pop() # 스택 맨 위에 있는 값 pop으로 제거

result = 0 # 결과값 저장할 변수 생성
count = 0 # 비교값 생성
# 아래 과정을 통해 카운트리스트에서 1이 가장 많이 반복된 길이를 찾아 결과값에 저장한다.
for n in cnt: # 카운트 리스트에서 값 하나씩 가져옴
    if n == 1: # 만약 가져온 값이 1이라면
        count += 1 # 비교값 + 1
        result = max(result, count) # 비교값과 결과값 중 더 큰 값을 결과값에 저장
    else: # 만약 가져온 값이 1이 아니라면
        count = 0 # 비교값을 0으로 초기화

print(result) # 결과값 출력

---

실행 화면

 

---

채점 결과