기초 알고리즘 -괄호(3)

괄호 문자열은 (, ) 두 괄호만으로 이루어진 문자열이다.이 중에서 ()처럼 제대로 배치된 문자열은 VPS이고, vps끼리 접합시켜도 vps이다.

즉, 처음과 끝이 ()로 닫혀있어야만 한다.

논리적인 구조로 볼 때, 여기서 해석할 수 있는 것은 무엇일까?

• 처음과 끝이 닫히므로 n번째에 ')'가 나오면 n-1번째 까지의 '('의 갯수와 비교해 n번째까지의 ')' 갯수가 같거나 적어야한다.
• 입력받은 문자열의'('와 ')'의 갯수가 같고, 처음이 '('이고 끝이 ')'이면 YES이다.
• '('와 ')'의 갯수가 다르거나, 처음이 ')' or 마지막이'('이면 NO이다.

VPS라면 YES, 아니라면 NO를 출력한다.

아쉽지만 틀리고 말았다. 좀만 더 생각해볼까 했는데, 스택을 통해서 풀 수가 있겠다는 생각이 들어서 빠르게 그만뒀다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;

public class Hello_world {
	static StringBuilder sb = new StringBuilder();

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		
		while(T-->0) {
			String str = br.readLine();
			check(str);
		}
		System.out.println(sb);
		
	
	
	}
//')'가 들어갈 수 있는지 검증하는 메소드 
public static void check(String str) {
	//처음과 끝이 ')'이거나 '('이면 NO 출력.
	if(str.charAt(str.length()-1) == '(' || str.charAt(0) == ')') {
		sb.append("NO").append('\n');
	} else {
		for(int i =0; i<str.length(); i++) {
			int count = 0;
			int count_2 = 0;
			
			for(int j=0; j<=i; j++) {
				
				if(str.charAt(j) == ')') {
					count_2++;
				} else if(str.charAt(j) =='(') {
					count++;
				}
				
				if(count_2 > count) {
					sb.append("NO").append('\n');
					break;
				}
			}
			
			if(count_2 > count) {
				break;
			}
			else if(count == count_2 && i==str.length()-1) {
				sb.append("YES").append('\n');
				break;
			} else {
				continue;
			}
			
			
		}
		
	}	
}

}

스택을 활용한 방법이다.
이 방법을 진작에 생각해야했다. stack의 원리를 제대로 이해하고 있었다면 가능했을 것이다. 조금 더 문제를 풀기전에 어떤 메소드, 어떤 변수, 어떤 생성자를 활용해 문제를 풀어나갈지 논리적으로 풀어나가는게 중요한 것을 다시 생각한다.

항상 그렇게 생각하지만 마음대로 안되는건 안 비밀 ㅋ.
출처 : Stranger's lab

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.Stack;
 
public class Hello_world {
 
	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);
			}
 

	
			else if (stack.empty()) {
				return "NO";
			}
		
			else {
				stack.pop();
			}
		}
		if (stack.empty()) {
			return "YES";
		} 
		else {
			return "NO";
		}
	}
}