급식 안내문 묶음 검사

문제

학교 급식 담당자는 학생에게 보여 줄 급식 안내문을 만들기 전에 안내문 편집 기록을 검사한다. 실제 음식 이름은 별도 자료에 저장되어 있으며, 검사에 사용하는 기록에서는 음식 한 개를 모두 소문자 x로 나타낸다. 같은 음식이 여러 번 등장할 수도 있으므로 x가 연속해서 나오는 것은 허용한다. 안내문에는 세 종류의 묶음이 있다. 일반 안내 묶음은 (와 ), 배식 안내 묶음은 [와 ], 주의 안내 묶음은 {와 }로 표시한다. 여는 기호를 만나면 해당 묶음이 시작되고, 닫는 기호를 만나면 해당 묶음이 끝난다. 하나의 묶음 안에 다른 묶음을 넣을 수 있으며, 어떤 묶음에도 속하지 않는 음식을 기록하거나 여러 묶음을 나란히 기록하는 것도 허용한다. 다만 모든 묶음에는 음식이 적어도 한 개 들어 있어야 한다. 안쪽 묶음에 들어 있는 음식도 바깥쪽 묶음에 들어 있는 것으로 센다. 검사기는 기록을 왼쪽부터 한 글자씩 읽는다. x와 여는 기호는 항상 받아들인다. 닫는 기호를 읽었을 때 아직 끝나지 않은 묶음이 없거나, 가장 최근에 시작하여 아직 끝나지 않은 묶음의 종류와 맞지 않으면 그 위치에서 오류를 발견한다. 종류가 맞더라도 그 묶음 안에서 음식을 하나도 읽지 않았다면 그 위치에서 오류를 발견한다. 오류를 발견하면 이후 글자는 검사하지 않는다. 모든 글자를 받아들인 뒤에도 끝나지 않은 묶음이 남아 있다면 기록 바로 다음 위치에서 오류를 발견한 것으로 처리한다. 기록의 길이가 N이면 이 위치의 번호는 N+1이다. 모든 묶음이 정상적으로 끝났다면 올바른 기록이다. 정규식 기능을 사용하지 않고 위 절차에 따른 검사기를 구현하여, 오류를 처음 발견하는 위치를 구하는 프로그램을 작성한다. 글자 위치는 왼쪽부터 1번으로 센다.

입력

첫째 줄에 기록의 길이인 정수 N이 주어진다. 1 ≤ N ≤ 200,000이다.
둘째 줄에 길이가 정확히 N인 문자열 S가 주어진다. S의 각 문자는 x, (, ), [, ], {, } 중 하나이며 공백은 없다.

출력

검사기가 오류를 처음 발견하는 위치를 정수 하나로 출력한다. 끝나지 않은 묶음 때문에 검사가 실패하면 N+1을 출력한다. 기록이 올바르면 0을 출력한다.

11
[x{xx}](xx)

0

6
x([x)]

5

4
{[x]

5

출처: Devin.KR 자체 제작