(JAVA) 백준 3986번 : 좋은 단어

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

3986번: 좋은 단어

 

문자열 처리 문제다.

 

Stack을 사용하는 것이 해결의 핵심이다.

 

문제에 대한 설명은 직접 확인하면 되고, 해결 방법만 작성해보겠다.

 

Stack 라이브러리를 사용하는 방법과

Stack을 array로 사용하는 방법

두 가지가 있는데, 첫 번째 방법으로 풀긴 했으나 시간이 오래 걸려서

두 번째 방법을 사용하니 절반으로 줄었다고 한다..!!

첫 번째 방법과 두 번째 방법 둘 다 적겠지만, 참고하실때는 두 번째 방법으로 참고하기 바란다.

 

 

 

 

첫 번째 방법 - Stack 라이브러리를 사용

 1) Stack에 첫 번째 문자를 push한다.

 2) 문자열의 두 번째부터 끝까지 탐색하면서

 3) Stack.peek() (Stack의 Top) 로 나온 문자와 현재 탐색하고 있는 문자와 비교한다.

 4-1) 같으면 Stack.pop()

 4-2) 다르면 Stack.push()

 5) 전부 탐색한 후 Stack.isEmpty()를 통해 Stack이 비어있으면 좋은 단어, 비어있지 않으면 좋지 않은 단어가 된다.

 

두 번째 방법 - Array 사용

 1) 문자열 길이만큼 char Array 생성

 2) Stack의 size를 나타내는 변수 0으로 초기화

 3) 문자열의 첫 번째부터 끝까지 탐색하면서

 4-1) size가 0이면 Array[size]에 i 번째의 문자를 넣고, size를 1 증가시킨다.

 4-2) size가 0이 아닐 때, Array[size - 1] 에 담긴 문자와 i 번째의 문자가 같으면 size를 1 감소시킨다. (= pop)

 4-3) size가 0이 아닐 때, Array[size - 1] 에 담긴 문자와 i 번째의 문자가 다르면 Array[size]에 문자를 넣고, size를 1 증가시킨다. (= push)

 5) 전부 탐색한 후 size가 0이면 좋은 단어, 0이 아니면 좋지 않은 단어이다.

 

 

 

과정은 이렇게 진행된다.

간-단!

 

 

 

첫 번째 방법 소스코드

---

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

// 좋은 단어
// 문자열 처리 문제 -> Stack 사용
public class p3986 {
	public static void main(String args[]) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int n = Integer.valueOf(st.nextToken());
		int count = 0;
		for(int i = 0; i < n; i++) {
			String str = br.readLine();
			Stack<Character> stack = new Stack<Character>();	
			int len = str.length();
			stack.push(str.charAt(0));
			
			for(int j = 1; j < len; j++) {
				char nowCh = str.charAt(j);
				if(!stack.isEmpty()) {
					char prevCh = stack.peek();
					if(prevCh == nowCh) {	// top의 문자와 같으면 pop
						stack.pop();
						continue;
					}
				}
				stack.push(nowCh);
			}
			
			if(stack.isEmpty()) {	// 좋은 단어
				count++;
			}
		}
		System.out.println(count);
	}
}

 

두 번째 방법 소스코드

---

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

// 좋은 단어
// 문자열 처리 문제 -> Stack을 array로 사용
public class p3986 {
	public static void main(String args[]) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int n = Integer.valueOf(st.nextToken());
		int count = 0;
		for(int i = 0; i < n; i++) {
			String str = br.readLine();	
			int len = str.length();
			char[] stack = new char[len]; 
			int stackLen = 0;
			
			for(int j = 0; j < len; j++) {
				char nowCh = str.charAt(j);
					if(stackLen == 0) {
						stack[stackLen] = nowCh;
						stackLen++;
					}
					else if(stack[stackLen- 1] == nowCh) {	// 이전 문자와 현재 문자가 같으면
						stackLen--;	// pop
					}
					else {
						stack[stackLen] = nowCh;
						stackLen++;
					}
			}
			if(stackLen == 0) {
				count++;
			}
		}
		System.out.println(count);
	}
}

 

 

 

깃허브로 소스코드 보기