19244번 - 괄호 문자열 서브태스크다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 (하단 참고) | 256 MB | 63 | 27 | 20 | 41.667% |
문제
"괄호 문자열"은 우리가 흔히 사용하는 여섯 개의 괄호 기호들 ("(", ")", "[", "]", "{", "}")로만 구성된 문자열을 일컫는다.
그 중 "균형잡힌" 괄호 문자열은 아래 조건에 따라 정의된다.
- "()" "[]" "{}" 이 셋은 균형잡힌 괄호 문자열이다.
- 문자열 "X"와 "Y"가 균형잡힌 괄호 문자열이라면 "XY" 와 "YX"도 균형잡힌 괄호 문자열이다.
- 문자열 "Z"가 균형잡힌 괄호 문자열이라면 앞/뒤로 "("과")" 혹은 "{"과"}" 혹은 "["과"]"을 붙인 문자열 "(Z)" 혹은 "{Z}" 혹은 "[Z]"도 균형잡힌 문자열이다.
- 마지막으로, 편의상 길이가 0인 "" 문자열도 균형잡힌 괄호 문자열이다. (예제 참고)
예를 들어 "[](){}", "[[()]]", "{}[()]" 은 균형잡힌 괄호 문자열이고, "[][[", "()(}", "{]" 은 균형잡힌 괄호 문자열이 아니다.
우리가 다룰 문자열은 와일드카드 ("*")를 포함할 수 있는데, 각 와일드카드는 여섯 개의 괄호 기호 중 하나로 대체될 수 있다. 예를들어 S = "[**)" 라는 문자열을 생각해보자. 첫 번째 와일드카드를 "]"로 대체하고 두 번째 와일드카드를 "("로 대체하면 S' = "[]()" 라는 새로운 문자열을 얻을 수 있고, 이는 균형잡힌 괄호 문자열이다. 만약 첫 번째 와일드카드를 "("로 대체하고 두 번째 와일드카드를 "]"로 대체하면 바뀐 문자열은 S'' = "[(])"가 되고 이는 균형잡힌 괄호 문자열이 아니다.
상기한 괄호 기호와 와일드카드로만 구성된 문자열이 입력으로 주어졌을 때, 당신은 이 문자열을 (가능한 길이가 가장 긴) 균형잡힌 괄호 문자열로 바꾸고 싶다. 이를 위해 일부 문자는 지워야 할 수 있고, 각 와일드카드는 당신이 임의로 여섯 개의 괄호 기호 중 하나로 바꿀 수 있다 (혹은 필요 없다면 지울 수 있다). 예를 들어 입력 문자열이 A = "***" 인 경우를 생각해보자. 균형잡힌 괄호 문자열의 길이가 홀수일 수 없으므로 세 글자 중 한 글자를 지우고, 남은 두 개의 와일드카드는 "()" 혹은 "[]" 혹은 "{}"로 대체하여 길이가 2인 균형잡힌 괄호 문자열을 만들 수 있다. 다른 예로 B = "[{([" 인 경우 상기한 4번 조건에 해당하는 길이가 0인 균형잡힌 괄호 문자열을 얻을 수 있지만, 길이가 더 긴 균형잡힌 괄호 문자열을 얻는 것은 불가능하다. 마지막으로 C = "(]{}){([)}" 인 경우, 대괄호 기호 두 개 ("]"와 "[")를 제거하면 길이가 6인 균형잡힌 괄호 문자열 "({}){()}"을 얻을 수 있다.
위와 같이 와일드카드와 여섯 개의 괄호 기호들로만 구성된 문자열이 입력으로 주어졌을 때, 가장 긴 균형잡힌 괄호 문자열을 얻기 위해 지워야 하는 문자의 (최소) 개수를 출력하는 프로그램을 작성하시오.
입력
첫 줄에 테스트 케이스의 수 T가 주어진다.
각 줄에 문자열이 하나씩 주어진다.
출력
각 테스트 케이스에 대하여 최소 몇 개의 문자를 지워 균형잡힌 괄호 문자열을 얻을 수 있는지 출력한다.
제한
- 1 ≤ T ≤ 10
- 1 ≤ 문자열 길이 ≤ 500
서브태스크 1 (6점)
- 입력으로 주어지는 문자열은 문제에 언급된 여섯 종류의 괄호 기호 중 한 종류만을 포함하며 와일드카드는 주어지지 않는다. (즉 "[]" 혹은 "()" 혹은 "{}" 쌍만 포함된 문자열만 주어진다.)
서브태스크 2 (16점)
- 입력으로 주어지는 문자열은 문제에 언급된 여섯 종류의 괄호 기호와 와일드카드만 포함한다.
예제 입력 1
6
***
[{([
(]{}){([)}
**(][)
(*]*[)
[]
예제 출력 1
1 4 2 2 2 0
- 테스트 케이스 1, 2, 3: 문제에서 다룬 예시이다.
- 테스트 케이스 4: 와일드카드를 임의의 괄호 한 쌍으로 대체하고 (가령 "{}") 이후에 등장하는 대괄호 "][" 두 글자를 지우면 길이가 4인 균형잡힌 괄호 문자열을 얻을 수 있다.
- 테스트 케이스 5: 다양한 방법이 존재하는데, 대괄호 두 글자를 지우고 와일드 카드를 활용하여 "()()" 를 얻을 수 있다. 다른 방법으로 첫 번째 와일드 카드를 "["로 대체하고, 두 번째 와일드 카드와 그 직후에 나오는 "["를 지워 "([])"를 얻을 수도 있다. 길이가 6인 균형잡힌 괄호 문자열을 얻을 수 있는 방법이 없으므로 이 방법이 최적이다.
- 테스트 케이스 6: 입력 문자열이 이미 균형잡힌 괄호 문자열인 경우 0개의 글자를 지우는 것이 최선이므로 0을 출력한다.
시간 제한
- Java 8: 1 초
- Python 3: 4 초
- PyPy3: 4 초
- Java 8 (OpenJDK): 1 초
- Java 11: 1 초
- Python 2: 4 초
- PyPy2: 4 초
- Kotlin (JVM): 1 초
- Java 15: 1 초
채점 및 기타 정보
- 예제는 채점하지 않는다.
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호