https://www.acmicpc.net/problem/4949
4949번: 균형잡힌 세상
각 문자열은 마지막 글자를 제외하고 영문 알파벳, 공백, 소괄호("( )"), 대괄호("[ ]")로 이루어져 있으며, 온점(".")으로 끝나고, 길이는 100글자보다 작거나 같다. 입력의 종료조건으로 맨 마지막에
www.acmicpc.net
4949, 균형잡힌 세상
[ 난이도 : 실버 4 ]
이번 문제는 스택을 사용해서 풀어보겠다.
# Process
input
: 입력받은 String 이 "." 이 아닐 때까지 입력을 받고 solve 라는 메서드를 통해 답을 도출한다.
static String str;
static void input()
{
while(true)
{
str = scan.nextLine();
if(str.equals(".")) break;
sb.append(solve(str)).append('\n');
}
System.out.println(sb);
}
solve()
: 입력받은 String 을 순회하며 "(", "[" 의 경우 stack 에 push 한다.
닫는 소괄호 ("]", ")") 의 경우에
1. "]"
: 스택이 비어있는 지 확인 & 들어있는 원소가 "["인지 확인
2. ")"
: 스택이 비어있는 지 확인 & 들어있는 원소가 "("인지 확인
이 두가지를 경우를 고려하면 된다.
쌍을 이루고 균형을 이루어야 하기 때문에 닫는 괄호가 나오는 경우에는 매칭이 되는 원소를 peek() 로 확인하는 과정이라고
이해하면 될 것 같다.
static String solve(String s)
{
Stack<Character> stack = new Stack<>();
for(int i = 0; i < s.length(); i++)
{
char c = s.charAt(i); // i 번째 문자
// 여는 괄호일 경우 스택에 push
if(c == '(' || c == '[')
{
stack.push(c);
}
// 닫는 소괄호 일 경우
else if(c == ')')
{
// 스택이 비어있거나 pop할 원소가 소괄호랑 매칭이 안되는 경우
if(stack.empty() || stack.peek() != '(')
return "no";
else
stack.pop();
}
else if(c == ']')
{
// 스택이 비어있거나 pop할 원소가 대괄호랑 매칭이 안되는 경우
if(stack.empty() || stack.peek() != '[')
return "no";
else
stack.pop();
}
// 그 외의 경우에는 불필요한 문자들이기에 skip한다.
}
if(stack.empty())
return "yes";
else
return "no";
}
전체 코드
static String str;
static void input()
{
while(true)
{
str = scan.nextLine();
if(str.equals(".")) break;
sb.append(solve(str)).append('\n');
}
System.out.println(sb);
}
static String solve(String s)
{
Stack<Character> stack = new Stack<>();
for(int i = 0; i < s.length(); i++)
{
char c = s.charAt(i); // i 번째 문자
// 여는 괄호일 경우 스택에 push
if(c == '(' || c == '[')
{
stack.push(c);
}
// 닫는 소괄호 일 경우
else if(c == ')')
{
// 스택이 비어있거나 pop할 원소가 소괄호랑 매칭이 안되는 경우
if(stack.empty() || stack.peek() != '(')
return "no";
else
stack.pop();
}
else if(c == ']')
{
// 스택이 비어있거나 pop할 원소가 대괄호랑 매칭이 안되는 경우
if(stack.empty() || stack.peek() != '[')
return "no";
else
stack.pop();
}
// 그 외의 경우에는 불필요한 문자들이기에 skip한다.
}
if(stack.empty())
return "yes";
else
return "no";
}
static void pro()
{
}
public static void main(String[] args)
{
input();
pro();
}