[백준] 3986번 : 좋은 단어

문제

A와 B로만 이루어진 문자열이 주어졌을 때

같은 글자끼리 선을 그어 교차하지 않고 모두 맞아떨어지는 경우

주어진 문자열을 좋은 단어라고 판단하고

좋은 단어가 몇개인지 출력하는 문제

 

접근 방식

좋은 단어에 대한 설명이 헷갈릴 수 있는데 아래와 같다.

 

AABB (O)

ABBA (O)

ABAB (X)

 

알 수 있는 사실은 연속해서 존재하거나 중간에 다른 단어의 선과 겹치면 안 된다는 건데

같은 경우 빼주고 같지 않은 경우는 넣어주면 되므로 스택을 사용하면 쉽게 풀 수 있다.

 

ABBA 같은 경우만 신경 써서 풀면 되는 문제로

아래와 같은 순서로 실행되는 코드를 짜면 된다.

 

Stack<Character> stack = new Stack<>();

// ABBA

stack.push('A');	// stack(A)
peek() == 'B';	// 'A' == 'B'
stack.push('B');	// stack(A, B)
peek() == 'B';	// 'B' == 'B'
stack.pop();	// stack(A)
peek() == 'A';	// 'A' == 'A'
stack.pop();	// stack()

 

위와 같은 과정을 거치면 좋은 단어인 경우에는

스택에 아무런 값도 남지 않기 때문에

스택이 비었을 때 좋은 단어의 카운트를 1씩 증가시켜 주면 된다.

 

 

풀이

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int n = Integer.parseInt(br.readLine());

		int result = 0;

		for (int i = 0; i < n; i++) {
			char[] word = br.readLine().toCharArray();

			Stack<Character> stack = new Stack<>();

			for (char c : word) {
				if (stack.isEmpty()) {
					stack.push(c);
				} else {
					char top = stack.peek();
					if (top == c){
						stack.pop();
					} else {
						stack.push(c);
					}
				}
			}

			if (stack.isEmpty()) {
				result++;
			}
		}

		System.out.println(result);
	}
}