1218번 - 괄호 짝짓기

문제의 저작권은 SW Expert Academy에 있습니다.

1. 문제
   1-1. 링크
   1-2. 문제 해석
2. 코드
3. 실행시간

 

 

 

---

 

 

1. 문제

1-1. 링크

SW Expert Academy

 

1-2. 문제 해석

stack에 괄호를 하나씩 하나씩 넣으면서 검사하면 되는 문제다.

나올 수 있는 경우의 수를 정리하면 쉽게 풀 수 있다.

 

• 여는 괄호가 나오는 경우
• 닫는 괄호가 나오는 경우

우선 크게 두 가지로 분류할 수 있다.

여는 괄호가 나오는 경우는 아무리 뒤죽박죽 나와도 상관없기 때문에 바로 stack에 추가하면 된다.

하지만 닫는 괄호는 다음과 같이 따져야 할 상황들이 있다.

 

• stack이 비어있는 경우
  • stack이 비어있는데 닫는 괄호가 들어갈 차례라는 건 아무리 난리부르스를 쳐도 괄호의 짝이 맞을 수 없다.
• 스택의 top에 짝이 맞지 않는 괄호가 있는 경우
  • 죽었다 깨어나도 괄호의 짝이 맞을 수 없다. 더 이상 검사할 가치가 없음
• 스택의 top에 짝이 맞는 여는 괄호가 있는 경우
  • 이 경우 top에 있는 괄호를 pop 하고 다시 포문을 이어가면 된다.

 

이 3가지 경우에 유의하며 코드를 짜면 된다.

그리고 마지막으로 다음과 같은 예외 상황이 있다.

 

• 괄호를 다 추가할 때까지 아무런 문제가 없었지만 스택에 괄호가 남아있는 경우
  • 여는 괄호의 수가 닫는 괄호의 수보다 많아서 짝이 다 매칭 되지 않은 상황이다.

 

이 문제의 테스트 케이스에는 위 상황이 주어지지 않았기 때문에 꼭 처리하진 않아도 된다.

하지만 원래는 처리해줘야 하는게 맞음!

 

그 외에 내가 적용한 팁(?)은 

괄호의 짝이 맞지 않는다고 판단 됐을 때 반복문을 빠져나가는 것보다

따로 메서드를 만들어서 리턴하는 것이 코드가 깔끔해진다.

또, 괄호의 짝을 비교할 때 HashMap을 이용하면 더 깔끔해진다.

 

 

2. 코드

public class Day4_1218_괄호짝짓기 {
        static Map<Character, Character> map = new HashMap<>();
	static Stack<Character> stack = new Stack<Character>();
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		map.put(')', '(');
		map.put(']', '[');
		map.put('}', '{');
		map.put('>', '<');
		
		for (int tc = 1; tc <= 10; tc++) {
			int len = Integer.parseInt(br.readLine());
			String str = br.readLine();
			stack.clear();
			int validity = 1;
			
			for(int i=0; i<len; i++) {
				if(!addParenthese(str.charAt(i))) {
					validity = 0; // 유효성 출력
					break;
				}
			}
			if(!stack.isEmpty()) validity = 0; // 스택에 괄호가 남은 경우
			sb.append("#" + tc + " " + validity + "\n");
		}
		
		System.out.println(sb.toString());
	}
	
	public static boolean addParenthese(char ch) {
		if(map.containsKey(ch)) { // 닫는 기호라면
			if(stack.isEmpty()) return false;
			if(map.get(ch) != stack.peek()) return false;
			else {
				stack.pop();
				return true;
			}
		}
		
		stack.add(ch); // 여는 기호는 그냥 추가
		return true;
	}
}

 

 

3. 실행시간

실행시간 경쟁 치열한거 보세요... ㄷㄷㄷ

 

이번에는 쉬운 문제여서 코드가 다 비슷한지 실행시간이 거의 비슷했다.

근데 왜 같은 101ms 중에서 내가 메모리랑 코드 길이가 제일 나은데 4등인지 모르겠다.

뭐야 내 2등 돌려줘요 😭😭