SWEA 1218. 괄호 짝짓기(JAVA)

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV14eWb6AAkCFAYD 

SW Expert Academy

 

 

 

문제)

 

 

풀이)

 

효율적이지는 않지만 정말 간단하게 생각했다.

짝이 알맞게 다 있다면 [, {, (, < 의 각각의 짝들이 다 있을거니까,

boolean 배열을 이용하여 각 괄호의 짝을 찾아주는 작업을 했다.

 

내가 푼 코드에 따르면 괄호의 위치와는 상관이 없다.

 

예를 들어, 코드에서 짝을 찾는 과정은 다음과 같다.

<

<

(

)

>

>

즉, 바깥쪽 <와 바깥쪽 >이 짝이 이루어지지 않는다는 것이다.

 

문제와의 의도와는 다르지만, 짝이 알맞게 있는지 없는지의 문제이므로 이렇게 풀어도 가능했다.

 

//import java.io.FileInputStream;
import java.util.Scanner;

public class Solution_D4_1218_괄호짝짓기 {

	public static void main(String[] args) throws Exception {
		//System.setIn(new FileInputStream("input.txt"));
		Scanner sc = new Scanner(System.in);
		for(int test_case = 1; test_case <= 10; test_case++)
		{
			int n = sc.nextInt();
			char[] arr = new char[n];	//input 배열
			boolean[] bool = new boolean[n];	//false
			String input = sc.next();
			arr = input.toCharArray();
			
			int answer = -1;
			for(int i=0; i<n; i++) {
				if(bool[i]==false) {	//탐색되지 않았으면
					switch(arr[i]) {
					case '{':{
						bool[i] = true;	//탐색
						for(int j=i+1; j<n; j++) {
							if(arr[j] == '}'&&bool[j]==false) {	//짝 찾고, 짝이 안 찾아진 애면
								bool[j]=true;
								break;
							}
						}
					}
						break;
					case '[':{
						bool[i] = true;
						for(int j=i+1; j<n; j++) {
							if(arr[j] == ']'&&bool[j]==false) {
								bool[j]=true;
								break;
							}
						}
					}
						break;
					
					case '<':{
						bool[i] = true;
						for(int j=i+1; j<n; j++) {
							if(arr[j] == '>'&&bool[j]==false) {
								bool[j]=true;
								break;
							}
						}
					}
						break;
					
					case '(':{
						bool[i] = true;
						for(int j=i+1; j<n; j++) {
							if(arr[j] == ')'&&bool[j]==false) {
								bool[j]=true;
								break;
							}
						}
					}
						break;
						
					}//switch
				}//if
			}//for
			for(int i=0; i<n; i++) {
				if(bool[i] == false) {	// 짝 없는애 있으면 0
					answer = 0;
					break;
				}
			}
			if(answer == -1)	//초기값 -1이니 0이 안 되었다는 것은 모두 짝이 있다는 것
				answer = 1;
			System.out.println("#"+test_case+" "+answer);
		}//test_case
		sc.close();
	}//main
}

 

 

 

이 문제의 정석은 stack을 활용하여 문제를 푸는 것이다.

입력값을 탐색하면서 여는 괄호를 만나면 stack에 저장하고, 닫는 괄호를 만나면 저장했던 괄호를 pop하여 잘 매칭되는지 확인한다.

 

이때, pop한 괄호와 닫는 괄호가 일치하지 않으면 틀렸으므로 0을 출력한다!

 

이 방식으로 문제를 푼다면 문제에서 원하는 방식으로 괄호 짝을 맞추면서 확인할 수 있다!

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

public class Solution_D4_1218_괄호짝짓기 {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringBuilder sb = new StringBuilder();
		String opener = "<{([";//스택에 추가할 (시작)문자
		
		for (int tc = 1; tc <= 10; tc++) {
			
			int answer = 1;//기본값 1(유효)
			sb.append("#").append(tc).append(" ");
			
			int N = Integer.parseInt(br.readLine()); //괄호 개수
			String line = br.readLine(); 
			
			Stack<String> stack = new Stack<>(); //stack
			
			for (int i = 0; i < N; i++) {
				String item = line.substring(i, i + 1);  //괄호 하나
				
				if (opener.contains(item)) {//시작괄호 이면
					stack.push(item);
				} else {//끝괄호 이면
					boolean result = false;
					if (!stack.isEmpty()) {// 데이터가 있다면
						String prev = stack.pop();//스택의 끝에 저장된 시작괄호를 prev에 저장
						
						//끝괄호와 시작괄호 매칭 확인
						if (item.equals(">") && prev.equals("<")) {
							result = true;
						} else if (item.equals("]") && prev.equals("[")) {
							result = true;
						} else if (item.equals("}") && prev.equals("{")) {
							result = true;
						} else if (item.equals(")") && prev.equals("(")) {
							result = true;
						}
						
						if (!result) {// 안 맞음
							answer = 0; 
							break;
						}
					}
				}//끝괄호else
			}//for 입력N

			sb.append(answer).append("\n");
		}//tc
		System.out.println(sb);
	}//main
}