[알고리즘]Stack - 올바른 괄호

1. 올바른 괄호
괄호가 입력되면 올바른 괄호이면 “YES", 올바르지 않으면 ”NO"를 출력하는 프로그램

입력) 첫 번째 줄에 괄호 문자열이 입력됩니다.
출력) 첫 번째 줄에 YES, NO를 출력합니다.

 

 

참고) Stack, Queue

1. Stack(스택)

- LIFO(Last-in, First-out)

- 시간 복잡도

Insertion(삽입)/Deletion(삭제) : O(1)

Search(검색,탐색) : O(n)

- index 있음 // stack.get(i);

- push(), pop(), peek(), isEmpty(), get(), size(), lastElement(), firstElement() ...

 

2. Queue(큐)

- FIFO(First-in, First-out)

- 시간 복잡도

Insertion(삽입)/Deletion(삭제) : O(1)

Search(검색,탐색) : O(n)

- offer(), poll(), peek(), isEmpty(), contains(), size() ...

 

 

1) 

import java.util.Scanner;
import java.util.Stack;

public class Main { // stack - push(), pop()
	
	public static String solution(String str) {
		String answer = "YES";
		Stack<Character> stack = new Stack<>();
		
		for (char x : str.toCharArray()) { // '('는 push, ')'는 이전의 '('를 pop 
			if (x=='(') stack.push(x);
			else { // ')'
				if (stack.isEmpty()) return "NO"; // 비어있으면 바로 NO return
				stack.pop();
			}
		}	
		// '('가 남아있는 상황
		if (!stack.isEmpty()) return "NO";
		
		return answer;
	}

	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		String str = scanner.next();
		System.out.println(solution(str));
	}

}

 

2)

import java.util.Scanner;
import java.util.Stack;

public class Main {
	
	public static String solution(String str) {
		String answer = "NO";
		Stack<Character> stack = new Stack<>();
		
		for (int i=0; i<str.length(); i++) {
			stack.push(str.charAt(i));
			if (stack.firstElement()==')') return answer; // NO
			if (stack.lastElement()==')' && stack.get(stack.size()-2)=='(') {
				stack.pop(); // ')' pop
				stack.pop(); // '(' pop
			}
		}
		if (stack.empty()) return "YES";	
		
		return answer;
	}

	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		String str = scanner.next();
		System.out.println(solution(str));
	}

}

---

결과

입력
(()(()))(()

출력
NO