

알고리즘 분류
- 자료 구조
- 문자열
- 스택
예전에 풀어봤던 문제라
바로 스택이 떠올랐다..
괄호 문자열이 들어갈 때 스택에 차곡차곡 넣고 () 요렇게 겹치는 순간이 오면
pop 해주면 된다
전체 문자열을 돌고난 후 스택에 값이 없으면 VPS라서 "YES" 출력,
값이 하나라도 있으면 "NO" 출력이다.
Stack 사용
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
for (int i = 0; i < N; i++) {
Stack<Character> stack = new Stack<>();
String input = br.readLine();
char[] arr = input.toCharArray();
for (int j = 0; j < arr.length; j++) {
if (arr[j] == ')') {
if (stack.size() > 0) {
if (stack.peek() == '(') {
stack.pop();
} else {
stack.push(arr[j]);
}
}
else {
stack.push(arr[j]);
}
} else {
stack.push(arr[j]);
}
System.out.println(stack);
}
if (stack.size() == 0) {
System.out.println("YES");
} else {
System.out.println("NO");
}
}
}
}
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
for (int i = 0; i < N; i++) {
Stack<Character> stack = new Stack<>();
String input = br.readLine();
char[] arr = input.toCharArray();
for (int j = 0; j < arr.length; j++) {
if (arr[j] == ')') {
if (stack.size() > 0) {
if (stack.peek() == '(') {
stack.pop();
} // else 처리를 하지 않음
}
else {
stack.push(arr[j]);
}
} else {
stack.push(arr[j]);
}
System.out.println(stack);
}
if (stack.size() == 0) {
System.out.println("YES");
} else {
System.out.println("NO");
}
}
}
}
이 방법도 맞는데,
그 이유는 새로 ')'를 추가하지 않아도 어차피 마지막에
하나라도 남아 있으면 NO를 출력해서 답에는 타격이 없기 때문이다.
근데 둘 다 돌려보니 복잡도에는 별 차이가 없었다!
블로그 참조해보니
stack을 활용하되, empty()로 확인하는
그런 방법도 있었다!
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
int T = Integer.parseInt(br.readLine());
for(int i = 0; i < T; i++) {
sb.append(solve(br.readLine())).append('\n');
}
System.out.println(sb);
}
public static String solve(String s) {
Stack<Character> stack = new Stack<>();
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
// 여는 괄호일 경우 스택에 넣는다.
if (c == '(') {
stack.push(c);
}
// 스택이 비어있는 경우. 즉, 닫는 괄호를 입력받았으나 pop할 원소가 없을 경우
else if (stack.empty()) {
return "NO";
}
// 그 외의 경우 stack 원소를 pop 한다.
else {
stack.pop();
}
}
if (stack.empty()) {
return "YES";
}
else {
return "NO";
}
}
}
'Languages > Java' 카테고리의 다른 글
| [BOJ 길라잡이/Java] 11일차 #1966 프린터 큐 (0) | 2025.03.23 |
|---|---|
| [BOJ 길라잡이/Java] 9일차 #1874 스택 수열 (0) | 2025.03.21 |
| [BOJ 길라잡이/Java] 8일차 #10816 숫자 카드 2 (0) | 2025.03.18 |
| [BOJ 길라잡이/Java] 8일차 #10867 중복 빼고 정렬하기 (0) | 2025.03.18 |
| [BOJ 길라잡이/Java] 7일차 #11651 좌표 정렬하기 2 (0) | 2025.03.17 |