https://www.acmicpc.net/problem/4949
시간 1초, 메모리 128MB
input :
- 문자열이 주어진다.
- 입력의 종료조건으로 맨 마지막에 점 하나(".")가 들어온다.
output :
- 해당 문자열이 균형을 이루고 있으면 "yes"를, 아니면 "no"를 출력
조건 :
- 모든 왼쪽 소괄호("(")는 오른쪽 소괄호(")")와만 짝을 이뤄야 한다.
- 모든 왼쪽 대괄호("[")는 오른쪽 대괄호("]")와만 짝을 이뤄야 한다.
- 모든 오른쪽 괄호들은 자신과 짝을 이룰 수 있는 왼쪽 괄호가 존재한다.
- 모든 괄호들의 짝은 1:1 매칭만 가능하다. 즉, 괄호 하나가 둘 이상의 괄호와 짝지어지지 않는다.
- 짝을 이루는 두 괄호가 있을 때, 그 사이에 있는 문자열도 균형이 잡혀야 한다.
일단 조건중 5번째 조건을 더 생각했어야 한다. ([)] 이러한 경우 균형잡힌 문자열이 아니다.
짝을 이루는 괄호 사이의 문자열이 균형잡히지 않았기 때문이다.
기본적으로 괄호를 풀 때 변수 1개를 가지고 0부터 시작해서 0으로 끝나는 방식을 사용했는데. 이 문제에선 스택이 눈에 더 잘 보일거 같아서 그냥 배열을 이용했다.
풀고 난 지금 보니 변수의 값이 음수가 아닌지 확인 / 다른 괄호의 값이 어떤지 확인 하는 방식? 다시 생각해보니 더 헷갈리는 거 같기도 하고....
뭐 암튼 "(", "[" 이 입력 되면 ans 에 추가 하고 닫는 괄호들이 들어오면 현재 ans 스택에 존재하는 마지막 괄호와 비교해서 삭제를 하든, 아니면 break 를 걸든 하게 하자.
예외적인 상황이 두 가지 존재한다.
-
닫는 괄호 "]", ")" 가 먼저 나오는 경우에 break를 해야 한다. ans 배열의 길이가 0일 경우를 예외 처리 하자.
-
모든 문자열을 확인한 후 여는 괄호 "(", "[" 만 있는 경우를 판별 해야 한다.
생각 보다 조건이 많네...
암튼 그렇다.
import sys
n, k = map(int, sys.stdin.readline().split())
data = list(map(int, sys.stdin.readline().split()))
num = [0] * 100001
start, end, length, ans = 0, 0, 0, 0
while start <= end:
if end == n:
if length <= ans:
break
else:
num[data[start]] -= 1
start += 1
length -= 1
if num[data[start]] <= k:
ans = max(ans, length)
continue
num[data[end]] += 1
length += 1
end += 1
if num[data[end - 1]] > k:
while num[data[end - 1]] > k:
num[data[start]] -= 1
start += 1
length -= 1
else:
ans = max(ans, length)
print(ans)
