[BAEKJOON_9935 - JAVA] 문자열 폭발

문제

www.acmicpc.net/problem/9935

9935번: 문자열 폭발

 

 

풀이

• 예전에 풀었던 커서이동 문제와 유사.(Stack을 사용)
• 폭발 문자열의 앞에서부터 검사하기보다는 폭발 문자열의 뒤에서부터 검사.
  (첫글자부터 마지막글자까지 검사하는것보다 뒤에서부터 검사하는것이 횟수가 적을것이라 판단)
• 코드 작성은 20분 내외로 완료했지만, 2%에서 fail이 지속발생.
  → 검사 과정에서 Stack이 비어있는 경우가 발생.
  ※ 검사 조건문에 검사 대상의 길이를 체크하여 해결.
  ex) 검사할 문자열 s, 폭발 문자열 ss인 경우.
• 속도가 빠른 다른분들의 코드는 Stack을 사용하지 않고 char배열의 index를 활용해서 풀이한것을 볼 수 있었다.

 

 

과정

1. 입력받은 문자열을 char단위로 담을 Stack , 검사를 진행하는 동안 임시로 보관할 tempStack, 총 2개의 Stack 생성
2. 폭발 문자열을 뒤집어서 ArrayList<Character>에 삽입. (마지막 글자가 같을때 검사를 진행할 예정)
3. 문자열의 길이만큼 char를 Stack에 넣는다.
4. 폭발 문자열의 마지막 글자와 같은 char이 발견된 경우 검사 진행.
5. 앞서 Stack에 들어간 글자를 차례대로 꺼낸 뒤, char의 동일 여부 검사와 동시에 tempStack에 삽입
   (검사 도중 폭발 문자열이 아니라고 판단되는 경우 rollback을 위해 tempStack에 보관)
6. 리턴값의 길이가 0인 경우 "FRULA"출력.

 

 

알고리즘 지식

• String
• Stack

 

 

JAVA코드

package BaekJoon_2020_12_23__30;

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

/**
 * @packageName : BaekJoon_2020_12_23__30
 * @fileName : BJ_9935_문자열폭발.java
 * @author : Mingeon
 * @date : 2020. 12. 28.
 * @language : JAVA
 * @classification : String
 * @time_limit : 2sec
 * @required_time : 13:10 ~ 14:46
 * @submissions : 5
 * @description
 * 1. 초기화의 위치를 조심하자. (임시저장 스택의 초기화 덕분에 제출횟수 증가)
 * 2. 반례를 찾으며 본 코드들은 배열을 이용하는 방법도 존재했으며, 효율이 더 좋게 나타나는 것을 볼 수 있었다.
 * 3. 스택을 2개 쓰지않고 index로 한개의 스택만을 사용해도 풀이 가능.
 */

public class BJ_9935_문자열폭발 {

	static String str; // 문자열
	static String boomStr; // 폭발 문자열

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

		str = br.readLine();
		boomStr = br.readLine();
		// End of input

		String res = search();
		System.out.println((res.length() == 0) ? "FRULA" : res);
		br.close();
	}

	private static String search() {
		Stack<Character> stack = new Stack<Character>(); // 문자열을 담을 스택
		Stack<Character> tempStack = new Stack<Character>(); // 검사를 위해 임시로 담을 스택

		// boomstr의 char화한 배열 (뒤에서부터 검사할 예졍이므로, 반대순서로 삽입)
		ArrayList<Character> boomArr = new ArrayList<Character>();
		for (int i = 0; i < boomStr.length(); i++) {
			boomArr.add(boomStr.charAt(boomStr.length() - i - 1));
		}

		// 문자열의 길이
		for (int i = 0; i < str.length(); i++) {
			char c = str.charAt(i);

			// 스택에 삽입
			stack.push(c);

			// 검사 대상인 경우
			if (c == boomArr.get(0) && stack.size() >= boomStr.length()) {

				tempStack.clear(); // 스택 초기화
				for (char target : boomArr) {
					char temp = stack.pop(); // 검사 대상 추출
					tempStack.push(temp); // 스택에 임시로 삽입

					// 폭발문자열이 아닌 경우
					if (target != temp) {
						// 원상 복구(기존의 스택으로 이동)
						while (!tempStack.isEmpty()) {
							stack.push(tempStack.pop());
						}
						break;
					}
				}
			}
		}

		StringBuilder sb = new StringBuilder();
		while (!stack.isEmpty()) {
			sb.append(stack.pop());
		}
		sb.reverse();

		return sb.toString();
	}

}