[자바 알고리즘 문제풀이 입문] ch05. Stack, Queue(자료구조) : 1. 올바른 괄호

 

 

 

5.1. 올바른 괄호

 

문제 

입력된 괄호가 올바른 괄호이면 “YES", 올바르지 않으면 ”NO" 출력

(())() 는 괄호의 쌍이 올바르게 위치하는 것, (()()))은 올바른 괄호가 아님. 

 

입력

(()(()))(()

 

출력

NO

 

---

 

풀이

import java.util.*;

public class Main {
    public String solution(String str) {
        String answer = "YES";
        Stack<Character> stack = new Stack<>();
        
        for(char c : str.toCharArray()) {
            if(c == '(') stack.push(c);
            else {
                if(stack.isEmpty()) return "NO"; // 닫는 괄호가 더 많을 경우
                stack.pop(); // 상단의 문자를 꺼냄
            }
        }
        
        // 여는 괄호가 더 많을 경우
        if(!stack.isEmpty()) return "NO";

        return answer; 
    }

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

 

입력받은 문자열을 문자 하나씩 조회하며
여는 괄호인 경우 무조건 stack에 push 해 줌
닫는 괄호 면 pop() 메서드를 사용해 stack 상단의 문자를 빼준다.

닫는 괄호가 나왔는데 stack이 비어있다면
닫는 괄호가 더 많은 경우이므로 올바른 괄호가 아님
"NO"를 return 

만약 반복문이 종료되었는데 stack이 비어있지 않다면
여는 괄호가 더 많아서 stack에 남아있는 것
"NO"를 return 

이 조건에 모두 걸리지 않는다면 올바른 괄호인 것이므로 

"YES"를 return 

 

 

 

---

 

메모

• stack.pop()
• stack.isEmpty()