[Java알고리즘] 5-1. 올바른 괄호(Stack, Queue)
🌵 Stack ?
스택(Stack)은 "쌓다"라는 의미로, 데이터를 차곡차곡 쌓아 올린 형태의 자료구조이다.
위의 사진과 같이 데이터가 순서대로 쌓이며 가장 마지막에 삽입된 자료가 가장 먼저 삭제되는 구조를 가지고 있다.
또한, 스택은 정해진 방향으로만 쌓을 수 있고, top으로 정한 곳을 통해서만 접근할 수 있다.
새로 삽입되는 자료는 top이 가리키는 가장 맨 위에 쌓이게 되며, 자료를 삭제할 때도 top을 통해서 삭제가 가능하다.
push
를 통해 삽입 연산을, pop
을 통해 삭제 연산을 할 수 있으며,
이러한 스택의 구조를 후입 선출
의 구조라고 한다.
줄여서 LIFO(Last In First Out)
이라고 부른다.
🥦 Queue?
큐(Queue)는 스택(Stack)과 다르게 먼저 들어온 것이 먼저 나가는 "선입선출" 구조로, FIFO(First In First Out)의 구조를 가지고 있다.
삭제 연산이 수행되는 곳을 프론트(front), 삽입 연산이 이루어지는 곳은 리어(rear)로, FIFO 구조를 위해 스택과 다르게 큐의 한쪽 끝에서는 삽입 작업이, 다른 한쪽 끝에서는 삭제 작업이 나뉘어서 이루어지고 있다.
큐는 리어(rear)에서 이루어지는 삽입 연산을 인큐(Enqueue)
라고 부르며, 프론트(front)에서 이루어지는 삭제 연산을 디큐(Dequeue)
라고 부른다.
🌼 Problem
🍔 Solution 1
import java.util.Scanner;
import java.util.Stack;
public class Main {
public static String Solution(String input){
String answer = "YES";
Stack<Character> st = new Stack<>();
for(char ch : input.toCharArray()){
if(ch=='('){
st.push('(');
}else if(!st.isEmpty()){
st.pop();
}else if(st.isEmpty()){
answer = "NO";
}
}
if(!st.isEmpty()){
answer = "NO";
}
return answer;
}
public static void main(String[] args) {
Scanner in=new Scanner(System.in);
String input = in.next();
System.out.println(Solution(input));
}
}
🍪 강사 Solution - 비슷하게 풀었다!
import java.util.Scanner;
import java.util.Stack;
public class Main {
// 강사
public static String Solution(String str){
String answer = "YES";
Stack<Character> stack = new Stack<>();
for(char x : str.toCharArray()){
if(x=='('){
stack.push(x);
}else{
// 닫는 괄호 ')'가 많은 경우, stack.pop으로 인해 stack이 비어있을 수 있다.
if(stack.isEmpty()) return "NO";
stack.pop();
}
}
// 여는 괄호 '('가 많은 경우, stack.pop이 모두 이뤄지지 못하여 stack이 비어있지 않음
if(!stack.isEmpty()){
return "NO";
}
return answer;
}
public static void main(String[] args) {
Scanner in=new Scanner(System.in);
String input = in.next();
System.out.println(Solution(input));
}
}
🍖Issue🍖
if(stack.isEmpty()) return "NO";
이 부분을 answer= "NO";
로 적으면 runtime error
가 발생한다.
아마 )
로 시작하는 문자열을 집어넣었을 때,
answer = "NO"
코드 뒤, stack.pop()
을 실행 할 수 없어서 생기는 문제접이라고 판단된다.
Author And Source
이 문제에 관하여([Java알고리즘] 5-1. 올바른 괄호(Stack, Queue)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@dingdoooo/Java알고리즘-5-1.-올바른-괄호Stack-Queue저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)