문제
여는 괄호와 닫는 괄호만으로 이루어진 문자열이 주어진다. 여기서 안정적인 문자열을 만들기 위한 최소 연산의 수를 구하려고 한다. 안정적인 문자열의 정의란 다음과 같다.
- 빈 문자열은 안정적이다.
- S가 안정적이라면, {S}도 안정적인 문자열이다.
- S와 T가 안정적이라면, ST(두 문자열의 연결)도 안정적이다.
{}, {}{}, {{}{}}는 안정적인 문자열이지만, }{, {{}{, {}{는 안정적인 문자열이 아니다.
문자열에 행할 수 있는 연산은 여는 괄호를 닫는 괄호로 바꾸거나, 닫는 괄호를 여는 괄호로 바꾸는 것 2가지이다.
입력
입력은 여러 개의 데이터 세트로 이루어져 있다. 각 데이터 세트는 한 줄로 이루어져 있다. 줄에는 여는 괄호와 닫는 괄호만으로 이루어진 문자열이 주어진다. 문자열의 길이가 2000을 넘는 경우는 없고, 항상 길이는 짝수이다.
입력의 마지막 줄은 '-'가 한 개 이상 주어진다.
출력
각 테스트 케이스에 대해서, 테스트 케이스 번호와 입력으로 주어진 문자열을 안정적으로 바꾸는데 필요한 최소 연산의 수를 출력한다.
풀이
입력받은 문자열에 대해 순차적으로 탐색해주며 안정적인 문자열( '{ }' )은 추가 연산이 필요하지 않으니 제거해주자.
stack의 오른쪽에서 push, pop해주며 안정적인 문자열이 만들어진다면 pop을, 만들어 지지 않는다면 push해주자.
이제 stack에는 불안정적인 문자열이 들어있을 것이다. ( ex: ' }}}{{{{{{{{ ')
문제에서 주어지는 문자열의 길이는 항상 짝수로 안정적인 문자열을 만들 수 있는 길이를 보장한다.
또한, 문제에서 주어진 조건 2번에 의하며 안정적인 문자열의 계층 구조 또한 안정적인 문자열로 볼 수 있다. 때문에 Greedy한 풀이가 가능하다.
stack의 요소를 두개씩 뽑아내면서 안정적인 문자열로 만드는데 필요한 연산의 수를 세주자.
직관적으로 이해하기 위해 이번에는 stack의 왼쪽에서 pop, push하겠다.
두개의 문자가 ' { { ' 또는 ' } } '라면 한 개만 뒤집어도 된다.
반면, ' } { ' 라면 순서를 변경할 수는 없다 때문에 둘 다 뒤집어야 한다.
소스코드
출처
4889번: 안정적인 문자열
입력은 여러 개의 데이터 세트로 이루어져 있다. 각 데이터 세트는 한 줄로 이루어져 있다. 줄에는 여는 괄호와 닫는 괄호만으로 이루어진 문자열이 주어진다. 문자열의 길이가 2000을 넘는 경우
www.acmicpc.net
'PS > Baekjoon Online Judge' 카테고리의 다른 글
| [백준 17952] 과제는 끝나지 않아! [Java] (1) | 2024.01.04 |
|---|---|
| [백준 01662] 압축 [Java] (1) | 2024.01.03 |
| [백준 16120] PPAP [Java] (1) | 2024.01.01 |
| [백준 02841] 외계인의 기타 연주 [Java] (1) | 2023.12.29 |
| [백준 02504] 괄호의 값 [Java] (1) | 2023.12.29 |