백준 10799번
https://www.acmicpc.net/problem/10799
괄호에 관련된 문제이다.
안 풀던 유형의 문제여서 생각보다 어려웠다
좋은 문제인 것 같다.
for (int i = 0; i < N; i++) {
char ch = chArr[i];
if (ch == '(') {
list.offerLast(ch);
} else if(ch == '1') {
ans += list.size();
} else {
list.pollLast();
ans++;
}
}
list
에서 '('로 저장된다. ['(', '(', '(']
라는 표시는 현재 진행중인 쇠막대기가 3개 있다는 뜻이다.
중간에 레이저가 나오면서 쇠막대기가 언제 끝날지 모르는 상태이다.
그래서 if(ch == '1')
의 경우에 모르는 상태지만 일단 레이저에 잘리는게 확정됨으로써
list.size()
에 있는 개수들이 확정으로 잘리게 됨으로 ans += list.size()
가 된다.
그리고 if(ch == ')')
의 경우 쇠막대기가 하나 끝나므로 잘린 쇠막대기의 끝부분 + 1을 해주면 된다. 그래서 ans++
import java.io.*;
import java.util.LinkedList;
public class Main {
// input
private static BufferedReader br;
// variables
private static char[] chArr;
public static void main(String[] args) throws IOException {
br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
input();
bw.write(solve());
bw.close();
} // End of main()
private static String solve() {
StringBuilder sb = new StringBuilder();
int ans = 0;
int N = chArr.length;
LinkedList<Character> list = new LinkedList<>();
for (int i = 0; i < N; i++) {
char ch = chArr[i];
if (ch == '(') {
list.offerLast(ch);
} else if(ch == '1') {
ans += list.size();
} else {
list.pollLast();
ans++;
}
}
sb.append(ans);
return sb.toString();
} // End of solve()
private static void input() throws IOException {
chArr = br.readLine().replace("()", "1").toCharArray();
} // End of input()
} // End of Main class