캠핑 안내문 검사기

문제

캠핑장에서는 작은 안내 화면에 표시할 문구를 직접 작성한다. 화면은 소문자로 된 설명과 괄호로 묶은 강조 구간을 지원한다. 관리자는 문구를 등록하기 전에 정규식 없이 문자를 왼쪽부터 읽는 검사기를 만들려고 한다. 문구에는 영문 소문자, 하이픈, 소괄호, 대괄호만 등장한다. 소괄호와 대괄호는 각각 같은 종류끼리 짝을 이루어야 한다. 닫는 괄호가 나올 때는 아직 닫히지 않은 괄호 중 가장 최근에 나온 여는 괄호와 짝을 이루어야 한다. 따라서 서로 다른 종류의 괄호가 엇갈리게 닫히면 올바르지 않다. 문구를 끝까지 읽은 뒤에는 닫히지 않은 괄호가 남아 있으면 안 된다. 하이픈은 단어를 연결하는 용도로만 사용한다. 각 하이픈의 바로 앞 문자와 바로 뒤 문자는 모두 영문 소문자여야 한다. 여기서 바로 앞뒤는 다른 문자를 건너뛰지 않은 원래 문구의 이웃한 위치를 뜻한다. 따라서 문구의 처음이나 끝에 하이픈이 있거나, 하이픈이 연속해서 나오거나, 하이픈 옆에 괄호가 있으면 올바르지 않다. 소문자는 다른 제한 없이 사용할 수 있으며, 괄호 안이 비어 있어도 된다. 문구 전체를 괄호로 감쌀 필요도 없다. 모든 규칙을 만족하는 문구는 등록할 수 있다. 등록할 수 있는 문구에 대해서는 강조 구간이 얼마나 깊게 겹치는지도 구한다. 겹침 깊이는 문구의 어떤 위치까지 읽었을 때 아직 닫히지 않은 여는 괄호 개수의 최댓값이다. 괄호가 전혀 없으면 깊이는 0이다. 주어진 문구의 등록 가능 여부와, 등록 가능할 때의 겹침 깊이를 출력하는 프로그램을 작성한다.

입력

첫째 줄에 문구의 길이인 정수 N이 주어진다. 둘째 줄에 길이가 정확히 N인 문자열 S가 주어진다. 1 ≤ N ≤ 200,000이다. S는 영문 소문자 a부터 z, 하이픈 -, 소괄호 (, ), 대괄호 [, ]로만 이루어지며 공백을 포함하지 않는다.

출력

등록할 수 있으면 VALID와 겹침 깊이를 공백으로 구분하여 한 줄에 출력한다. 등록할 수 없으면 INVALID만 한 줄에 출력한다.

15
camp([a-b])site

VALID 2

4
([)]

INVALID

4
a-[]

INVALID

출처: Devin.KR 자체 제작