[백준] 11899. 괄호 끼워넣기 (자바 JAVA)

[ 문제 ]  [백준] 11899. 괄호 끼워넣기 (자바 JAVA)

 

문제 링크 : https://www.acmicpc.net/problem/11899

11899번: 괄호 끼워넣기

---

# 접근 방법 및 풀이 

 

• 스택 기초 문제다.
• 올바른 괄호열이라면 '('일때 stack에 push하고 ')'일때 stack에서 pop해서 주어진 문자열을 다 탐색하고 난 뒤에 스택 사이즈는 0일 것이다.
• 그러나 문제에선 올바른 괄호열을 만들기 위해 필요한 최소 횟수이므로, 위의 특징을 알고 있다면 쉽게 풀 수 있다.
• 마찬가지로 '('일때 stack에 push하고, ')'일때 pop하는데, ')' 에서 pop하려고 할 때 스택이 비어있는 상태라면 이전에 '('가 필요하다. 따라서 횟수를 ++해준다.
• 다 탐색후에 스택 사이즈가 0이 아니라면 '(' 열린 괄호열이 ')'닫힌 괄호열 짝을 맞추지 못해 남아있으므로 횟수에 스택 사이즈를 더해준다.
• 자세한건 코드참조

# 주의할 점 

 

• 딱히 없음

 

JAVA 코드

package Silver;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;

public class bj11899_괄호끼워넣기 {

	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		String s = in.readLine();
		Stack<Character> stack = new Stack<>();
		int ans = 0;
		for (int i = 0; i < s.length(); i++) {
			char c = s.charAt(i);
			if(c == '(') {
				stack.add(c);
			}else {
				if(stack.empty()) {
					ans++;
				}else {
					stack.pop();
				}
			}
		}
		ans += stack.size();
		System.out.println(ans);
	}
}

 

 

 

REVIEW

오늘 코테보고 너무 힘들어서 쉬운걸 풀었다!