문제
{와 }로 이루어진 문자열을 안정적(올바른 괄호)으로 만들기 위해 변경해야 하는 최소 괄호 수를 구하라.
입력
여러 줄에 걸쳐 문자열이 주어지며, -로 시작하면 종료한다.
출력
각 문자열에 대해 "N. K" 형태로 최소 변경 수를 출력한다.
예제
| 입력 | 출력 |
|---|---|
}{ {}{} {{{} --- | 1. 2 2. 0 3. 1 |
풀이
열린 괄호 카운터를 추적하며, 매칭되지 않는 닫힌 괄호와 남은 열린 괄호의 변경 횟수를 합산한다.
- 문자열을 순회하며
{이면 카운터를 증가,}이면 감소시킨다 - 카운터가 0일 때
}가 나오면 변경이 필요하므로 카운트하고 카운터를 1로 설정한다 - 남은 열린 괄호는 문자열 끝에서 처리한다
핵심 아이디어: 매칭되지 않는 }는 즉시 {로 변경하고, 끝까지 남은 {는 변경해야 한다.
코드
package day749;
import java.io.*;
public class Day730BOJ4889안정적인문자열 {
static String line;
static char[] data = { '{', '}', '{', '}', '{', '}' };
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
int T = 1;
while (true) {
line = br.readLine();
if (line.toCharArray()[0] == '-')
break;
data = line.toCharArray();
boolean flag = false;
int cnt = 0;
int ans = 0;
for (int i = 0; i < data.length; i++) {
if (flag) {
if (data[i] == '{') {
ans++;
}
continue;
}
if (cnt == 0 && data[i] == '}') {
ans++;
cnt++;
continue;
}
if (data.length - i == cnt) {
if (data[i] == '{') {
ans++;
}
flag = true;
continue;
}
if (data[i] == '}') {
cnt--;
} else if (data[i] == '{') {
cnt++;
}
}
sb.append(T++ + ". " + ans + "\n");
}
System.out.println(sb);
}
}복잡도
- 시간: O(N)
- 공간: O(N)