[백준] 9935번 문자열 폭발 자바

문제

 

9935번: 문자열 폭발

 

 

문제 풀이

 

이 문제를 풀면서 자바의 String 관련 내장함수를 찾아보았는데, 생각보다 많은 함수들이 있었고 이걸 이용해서 문자열을 하나하나 탐색하고 갱신하면서 풀었다. 

 

- indexOf( ) : 문자열에서 특정 문자가 시작되는 인덱스 리턴

- substring(시작idx, 끝idx-1) : 문자열 중 특정 부분을 뽑아내 리턴

- startWith( ) : 문자열이 지정한 문자열로 시작하는지(인자값)

- replaceAll( ) : 문자열 중 특정 문자를 다른 문자로 바꾸고 싶을 때

- contains(str) : str문자열을 포함하고 있으면 true리턴

 

그치만 결과는 시간초과였다.

구글링해보니 스택을 이용해서 문자열을 따로 갱신하지 않고 바로 빼내면서 스택에 문자열을 담을 수 있었다.

시간 제한이 2초인데 아무래도 String값 자체를 조작하는게 시간이 많이 걸리는 것 같다.

알고리즘은

1. 스택에 문자열을 하나씩 담는다.

2. 스택사이즈가 폭발문자열 길이보다 크거나 같아지면 현재 스택값이 폭발 문자열의 맨 마지막 문자와 같은지 확인한다.

 2-1) 만약 두 문자가 같다면 스택에서 폭발문자열 길이만큼 pop으로 빼준다

 2-2) 만약 다르다면 다음 문자열을 계속해서 스택에 넣고 또 폭발열 마지막 문자와 확인

3. 마지막에 스택에 남은 문자들이 폭발문자열을 제거하고 남은 문자들이다.

 

❔왜 폭발문자열 마지막 문자부터 확인하는지

내 생각엔 스택 자료구조 상 처음 문자열이 같을 때 폭발열 길이만큼 추가로 스택에 넣고 확인 후 빼는 것보다 마지막으로 보고 빼는 게 더 편할 것 같아서 같다..

 

소스 코드

 

public class b_9935 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		String str = sc.next();
		String boom = sc.next();
		Stack<Character> stack = new Stack<Character>();

		for(int i = 0; i < str.length(); i++) {
			stack.push(str.charAt(i));
			
			//스택 사이즈가 폭발문자열만큼이 찼고, 스택 마지막 문자가 폭발문자열 마지막 문자와 같음 
			if(stack.size() >= boom.length() && stack.peek() == boom.charAt(boom.length()-1)) {
				//반대로 내려가면서 폭발문자열과 같은지 확인
				boolean isBoom = true;
				
                
                                //문자가 빠지면서 스택 인덱스가 계속 바뀌므로 
                    		//현재 인덱스 값에서 폭발열 길이만큼 뺀 후 1씩 더해가야 문자 확인 가능
				for(int j = 0; j < boom.length(); j++) {
					if(stack.get(stack.size()-boom.length()+j) != boom.charAt(j)) {
						isBoom = false;
						break;
					}
				}
				
				if(isBoom) {
					for(int j = 0; j < boom.length(); j++)
						stack.pop();
				}
			}
		
		}
		
		if(stack.size() == 0)
			System.out.println("FRULA");
		else {
			StringBuilder sb = new StringBuilder();
			for(int i = 0; i < stack.size(); i++)
				sb.append(stack.get(i));
			
			System.out.println(sb.toString());	
		}
	}

}