[SWEA] #1218 - 괄호 짝짓기

※ 문제에 대한 저작권은 SW Expert Academy에 있습니다.

💡 출처

---

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

SW Expert Academy

 

💡 문제

---

[설명]

4 종류의 괄호 문자들 '()', '[]', '{}', '<>'로 이루어진 문자열이 주어진다.

이 문자열에 사용된 괄호들의 짝이 모두 맞는지 판별하는 프로그램을 작성한다.

예를 들어 아래와 같은 문자열은 유효하다고 판단할 수 있다.

아래와 같은 문자열은 유효하지 않은 문자열이다. 붉은색으로 표시된 괄호의 짝을 찾을 수 없기 때문이다.

 

💡 아이디어

---

우선 괄호 문자들의 아스키코드를 보면 다음과 같다.

즉, 짝이 맞는 괄호끼리의 차이는 1 또는 2라는 것을 알 수 있다.

이 원리를 이용해 Stack이 비었을 땐 괄호를 PUSH 하고, 새로 들어오는 괄호와 Stack의 최상단에 있는 괄호의 차이가

1 또는 2일 땐 Stack의 최상단의 괄호를 POP 하게 된다.

주어진 테스트 케이스를 모두 사용했을 때 Stack이 비어있다면 모두 짝이 맞다고 볼 수 있다.

 

💡 소스코드

---

Type 1. Stack 사용

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

public class P_1218 {

	public static void main(String[] args) throws Exception {
		System.setIn(new FileInputStream("input.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		for (int TC = 1; TC <= 10; TC++) {
			int T = Integer.parseInt(br.readLine());
			int flag = 0;
			Stack<Character> stack = new Stack<>();

			String s = br.readLine();

			for (int i = 0; i < T; i++) {
				if (stack.empty())
					stack.push(s.charAt(i));

				else if (stack.peek() - s.charAt(i) == -1 || stack.peek() - s.charAt(i) == -2)
					stack.pop();

				else
					stack.push(s.charAt(i));
			}

			if (stack.empty())
				flag = 1;

			System.out.println("#" + TC + " " + flag);
		}
	}
}

 

Type 2. 괄호의 각 개수 Counting

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
 
class Solution {
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        for (int TC = 1; TC <= 10; TC++) {
            int T = Integer.parseInt(br.readLine());
            int flag = 0;
            int[] CountList = new int[8];
 
            String s = br.readLine();
 
            for (int i = 0; i < T; i++) {
                switch (s.charAt(i)) {
                case '(':
                    CountList[0]++;
                    break;
 
                case ')':
                    CountList[1]++;
                    break;
 
                case '<':
                    CountList[2]++;
                    break;
 
                case '>':
                    CountList[3]++;
                    break;
 
                case '[':
                    CountList[4]++;
                    break;
 
                case ']':
                    CountList[5]++;
                    break;
 
                case '{':
                    CountList[6]++;
                    break;
 
                case '}':
                    CountList[7]++;
                    break;
                }
            }
 
            if (CountList[0] == CountList[1] && CountList[2] == CountList[3] && CountList[4] == CountList[5]
                    && CountList[6] == CountList[7])
                flag = 1;
 
            System.out.println("#" + TC + " " + flag);
        }
    }
}

 

💡 결과

---

처음 문제를 풀 땐 단순히 괄호의 개수를 counting 해서 모든 괄호의 개수가 같다면 짝이 맞다고 판별했다.

(Type 2 코드 참고)

이후, Stack을 사용하는 코드로 변경했는데 이 코드에 문제가 조금 있다고 생각된다.

(Type 1 코드 참고)

그 이유는 아래의 그림에서 볼 수 있다.

이 그림에서 괄호의 짝은 모두 맞는 것을 알 수 있다.

하지만, Stack의 최상단만 확인해서는 이 케이스에선 통과할 수 없다.

그렇기 때문에 각 괄호의 개수를 Counting 하는 것이 더 올바른 풀이 방법이라고 볼 수 있을 것 같다.

내가 짠 코드가 통과한 이유는 아마 테스트 케이스가 매우 친절했던 것 같다....