시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 287 114 105 42.683%

문제

여는 괄호와 닫는 괄호만으로 이루어진 문자열이 주어진다. 여기서 안정적인 문자열을 만들기 위한 최소 연산의 수를 구하려고 한다. 안정적인 문자열의 정의란 다음과 같다.

  1. 빈 문자열은 안정적이다.
  2. S가 안정적이라면, {S}도 안정적인 문자열이다.
  3. S와 T가 안정적이라면, ST(두 문자열의 연결)도 안정적이다.

{}, {}{}, {{}{}}는 안정적인 문자열이지만, }{, {{}{, {}{는 안정적인 문자열이 아니다.

문자열에 행할 수 있는 연산은 여는 괄호를 닫는 괄호로 바꾸거나, 닫는 괄호를 여는 괄호로 바꾸는 것 2가지이다.

입력

입력은 여러 개의 데이터 세트로 이루어져 있다. 각 데이터 세트는 한 줄로 이루어져 있다. 줄에는 여는 괄호와 닫는 괄호만으로 이루어진 문자열이 주어진다. 문자열의 길이가 2000을 넘는 경우는 없고, 항상 길이는 짝수이다.

입력의 마지막 줄은 '-'가 한 개 이상 주어진다.

출력

각 테스트 케이스에 대해서, 테스트 케이스 번호와 입력으로 주어진 문자열은 안정적으로 바꾸는데 필요한 최소 연산의 수를 출력한다.

예제 입력 1

}{
{}{}{}
{{{}
---

예제 출력 1

1. 2
2. 0
3. 1

힌트

W3sicHJvYmxlbV9pZCI6IjQ4ODkiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM1NDhcdWM4MTVcdWM4MDFcdWM3NzggXHViYjM4XHVjNzkwXHVjNWY0IiwiZGVzY3JpcHRpb24iOiI8cD5cdWM1ZWNcdWIyOTQgXHVhZDA0XHVkNjM4XHVjNjQwIFx1YjJlYlx1YjI5NCBcdWFkMDRcdWQ2MzhcdWI5Y2NcdWM3M2NcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWM0IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YzVlY1x1YWUzMFx1YzExYyBcdWM1NDhcdWM4MTVcdWM4MDFcdWM3NzggXHViYjM4XHVjNzkwXHVjNWY0XHVjNzQ0IFx1YjljY1x1YjRlNFx1YWUzMCBcdWM3MDRcdWQ1NWMgXHVjZDVjXHVjMThjIFx1YzVmMFx1YzBiMFx1Yzc1OCBcdWMyMThcdWI5N2MgXHVhZDZjXHVkNTU4XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHVjNTQ4XHVjODE1XHVjODAxXHVjNzc4IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc1OCBcdWM4MTVcdWM3NThcdWI3ODAgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1YjJlNC48XC9wPlxyXG5cclxuPG9sPlxyXG5cdDxsaT5cdWJlNDggXHViYjM4XHVjNzkwXHVjNWY0XHVjNzQwIFx1YzU0OFx1YzgxNVx1YzgwMVx1Yzc3NFx1YjJlNC48XC9saT5cclxuXHQ8bGk+U1x1YWMwMCBcdWM1NDhcdWM4MTVcdWM4MDFcdWM3NzRcdWI3N2NcdWJhNzQsIHtTfVx1YjNjNCBcdWM1NDhcdWM4MTVcdWM4MDFcdWM3NzggXHViYjM4XHVjNzkwXHVjNWY0XHVjNzc0XHViMmU0LjxcL2xpPlxyXG5cdDxsaT5TXHVjNjQwIFRcdWFjMDAgXHVjNTQ4XHVjODE1XHVjODAxXHVjNzc0XHViNzdjXHViYTc0LCBTVChcdWI0NTAgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzU4IFx1YzVmMFx1YWNiMClcdWIzYzQgXHVjNTQ4XHVjODE1XHVjODAxXHVjNzc0XHViMmU0LjxcL2xpPlxyXG48XC9vbD5cclxuXHJcbjxwPnt9LCB7fXt9LCB7e317fX1cdWIyOTQgXHVjNTQ4XHVjODE1XHVjODAxXHVjNzc4IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc3NFx1YzljMFx1YjljYywgfXssIHt7fXssIHt9e1x1YjI5NCBcdWM1NDhcdWM4MTVcdWM4MDFcdWM3NzggXHViYjM4XHVjNzkwXHVjNWY0XHVjNzc0IFx1YzU0NFx1YjJjOFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViYjM4XHVjNzkwXHVjNWY0XHVjNWQwIFx1ZDU4OVx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YzVmMFx1YzBiMFx1Yzc0MCBcdWM1ZWNcdWIyOTQgXHVhZDA0XHVkNjM4XHViOTdjIFx1YjJlYlx1YjI5NCBcdWFkMDRcdWQ2MzhcdWI4NWMgXHViYzE0XHVhZmI4XHVhYzcwXHViMDk4LCBcdWIyZWJcdWIyOTQgXHVhZDA0XHVkNjM4XHViOTdjIFx1YzVlY1x1YjI5NCBcdWFkMDRcdWQ2MzhcdWI4NWMgXHViYzE0XHVhZmI4XHViMjk0IFx1YWM4MyAyXHVhYzAwXHVjOWMwXHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjNzg1XHViODI1XHVjNzQwIFx1YzVlY1x1YjdlYyBcdWFjMWNcdWM3NTggXHViMzcwXHVjNzc0XHVkMTMwIFx1YzEzOFx1ZDJiOFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LiBcdWFjMDEgXHViMzcwXHVjNzc0XHVkMTMwIFx1YzEzOFx1ZDJiOFx1YjI5NCBcdWQ1NWMgXHVjOTA0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWM1ZWNcdWIyOTQgXHVhZDA0XHVkNjM4XHVjNjQwIFx1YjJlYlx1YjI5NCBcdWFkMDRcdWQ2MzhcdWI5Y2NcdWM3M2NcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWM0IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc1OCBcdWFlMzhcdWM3NzRcdWFjMDAgMjAwMFx1Yzc0NCBcdWIxMThcdWIyOTQgXHVhY2JkXHVjNmIwXHViMjk0IFx1YzVjNlx1YWNlMCwgXHVkNTZkXHVjMGMxIFx1YWUzOFx1Yzc3NFx1YjI5NCBcdWM5ZGRcdWMyMThcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yzc4NVx1YjgyNVx1Yzc1OCBcdWI5YzhcdWM5YzBcdWI5YzkgXHVjOTA0XHVjNzQwICYjMzk7LSYjMzk7XHVhYzAwIFx1ZDU1YyBcdWFjMWMgXHVjNzc0XHVjMGMxIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWMsIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTQgXHViYzg4XHVkNjM4XHVjNjQwIFx1Yzc4NVx1YjgyNVx1YzczY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzQgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzQwIFx1YzU0OFx1YzgxNVx1YzgwMVx1YzczY1x1Yjg1YyBcdWJjMTRcdWFmYjhcdWIyOTRcdWIzNzAgXHVkNTQ0XHVjNjk0XHVkNTVjIFx1Y2Q1Y1x1YzE4YyBcdWM1ZjBcdWMwYjBcdWM3NTggXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI0ODg5IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiU2VpbmZlbGQiLCJkZXNjcmlwdGlvbiI6IjxwPkkmcnNxdW87bSBvdXQgb2Ygc3Rvcmllcy4gRm9yIHllYXJzIEkmcnNxdW87dmUgYmVlbiB3cml0aW5nIHN0b3JpZXMsIHNvbWUgcmF0aGVyIHNpbGx5LCBqdXN0IHRvIG1ha2Ugc2ltcGxlIHByb2JsZW1zIGxvb2sgZGlcdWZiMDNjdWx0IGFuZCBjb21wbGV4IHByb2JsZW1zIGxvb2sgZWFzeS4gQnV0LCBhbGFzLCBub3QgZm9yIHRoaXMgb25lLjxcL3A+XHJcblxyXG48cD5Zb3UmcnNxdW87cmUgZ2l2ZW4gYSBub24gZW1wdHkgc3RyaW5nIG1hZGUgaW4gaXRzIGVudGlyZXR5IGZyb20gb3BlbmluZyBhbmQgY2xvc2luZyBicmFjZXMuIFlvdXIgdGFzayBpcyB0byBcdWZiMDFuZCB0aGUgbWluaW11bSBudW1iZXIgb2YgJmxkcXVvO29wZXJhdGlvbnMmcmRxdW87IG5lZWRlZCB0byBtYWtlIHRoZSBzdHJpbmcgc3RhYmxlLiBUaGUgZGVcdWZiMDFuaXRpb24gZm9yIGJlaW5nIHN0YWJsZSBpcyBhcyBmb2xsb3dzOjxcL3A+XHJcblxyXG48b2w+XHJcblx0PGxpPkFuIGVtcHR5IHN0cmluZyBpcyBzdGFibGUuPFwvbGk+XHJcblx0PGxpPklmIFMgaXMgc3RhYmxlLCB0aGVuIHtTfSBpcyBhbHNvIHN0YWJsZS48XC9saT5cclxuXHQ8bGk+SWYgUyBhbmQgVCBhcmUgYm90aCBzdGFibGUsIHRoZW4gU1QgKHRoZSBjb25jYXRlbmF0aW9uIG9mIHRoZSB0d28pIGlzIGFsc28gc3RhYmxlLjxcL2xpPlxyXG48XC9vbD5cclxuXHJcbjxwPkFsbCBvZiB0aGVzZSBzdHJpbmdzIGFyZSBzdGFibGU6IHt9LCB7fXt9LCBhbmQge3t9e319OyBCdXQgbm9uZSBvZiB0aGVzZTogfXssIHt7fXssIG5vciB7fXsuIFRoZSBvbmx5IG9wZXJhdGlvbiBhbGxvd2VkIG9uIHRoZSBzdHJpbmcgaXMgdG8gcmVwbGFjZSBhbiBvcGVuaW5nIGJyYWNlIHdpdGggYSBjbG9zaW5nIGJyYWNlLCBvciB2aXNhLXZlcnNhLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+WW91ciBwcm9ncmFtIHdpbGwgYmUgdGVzdGVkIG9uIG9uZSBvciBtb3JlIGRhdGEgc2V0cy4gRWFjaCBkYXRhIHNldCBpcyBkZXNjcmliZWQgb24gYSBzaW5nbGUgbGluZS4gVGhlIGxpbmUgaXMgYSBub24tZW1wdHkgc3RyaW5nIG9mIG9wZW5pbmcgYW5kIGNsb3NpbmcgYnJhY2VzIGFuZCBub3RoaW5nIGVsc2UuIE5vIHN0cmluZyBoYXMgbW9yZSB0aGFuIDIwMDAgYnJhY2VzLiBBbGwgc2VxdWVuY2VzIGFyZSBvZiBldmVuIGxlbmd0aC48XC9wPlxyXG5cclxuPHA+VGhlIGxhc3QgbGluZSBvZiB0aGUgaW5wdXQgaXMgbWFkZSBvZiBvbmUgb3IgbW9yZSAmcnNxdW87LSZyc3F1bzsgKG1pbnVzIHNpZ25zLik8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCB0ZXN0IGNhc2UsIHByaW50IHRoZSBmb2xsb3dpbmcgbGluZTo8XC9wPlxyXG5cclxuPHByZT5rLiBOPFwvcHJlPlxyXG5cclxuPHA+V2hlcmUgayBpcyB0aGUgdGVzdCBjYXNlIG51bWJlciAoc3RhcnRpbmcgYXQgb25lLCkgYW5kIE4gaXMgdGhlIG1pbmltdW0gbnVtYmVyIG9mIG9wZXJhdGlvbnMgbmVlZGVkIHRvIGNvbnZlcnQgdGhlIGdpdmVuIHN0cmluZyBpbnRvIGEgYmFsYW5jZWQgb25lLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==