[백준] 3986번: 좋은 단어(문자열, 스택)

https://www.acmicpc.net/problem/3986

3986번: 좋은 단어

 

코드

import java.util.Scanner;
import java.util.Stack;

public class Main {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int N = scan.nextInt();
		Stack<Character> stack = new Stack<Character>();
		int goodWords = 0;

		for(int i=0; i<N; i++) {
			String str = scan.next();
			for(int j=0; j<str.length(); j++) {
				if(!stack.isEmpty() && str.charAt(j) == stack.peek()) 
					stack.pop();	// 현재 문자의 값과 stack의 top 값이 같을경우 => 짝을이루어 제거
				else 
					stack.push(str.charAt(j));	// 두 문자가 다를경우 => 스택에 쌓기.
			}
			// 모든 A, B가 짝이 맞을경우 -> 좋은단어
			if(stack.size() == 0)
				goodWords ++;

			stack.clear();	// 스택 초기화
		}

		System.out.println(goodWords);
		scan.close();
	}

}

풀이

* 선끼리 교차하지 않고, 각 글자를 정확히 한 개의 다른 위치에 있는 같은 글자와 짝 지을수 있으면 '좋은단어'

* A는 A끼리, B는 B끼리 쌍을 짓기로 한다.

 

 

위 그림에서는 선끼리 교차하므로 좋은 단어가 아니다.

 

스택을 이용해 해결한다.

ABAB에서 하나의 문자씩 비교를 해가며, 스택에 push나 pop을 하는데,

 

현재의 문자 값과 스택의 top 값이 동일하고, 스택이 비어있지 않으면 => 쌍을 지을 수 있으므로 스택에서 제거한다.

현재의 문자 값과 스택의 top 값이 다르면 => 쌍을 지을 수 없으므로 스택에 쌓는다.

 

위 과정을 반복해가며 스택이 비어있을 경우 => 모든 A, B는 쌍을 이루므로 좋은 단어이고,

스택이 비어있지 않은경우는 모든 A, B는 쌍을 이루지 않으므로 좋은 단어가 아니다.

그 후 스택의 값을 초기화한다.