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

14 Jun 2022 in Develop / Solving

java

문제 분석

• 문자열이 두 개 주어진다.
• 첫번째 문자열에서, 두번째 문자열을 지우고 새로운 문자열을 만듬.
• 첫 번째 문자열에 두 번째 문자열이 포함되는 한 반복하고, 결과를 출력할 것.

입력조건

문자열 1
문자열 2

풀이과정

• 그냥 replaceAll을 이용해서 문자열을 정리하다보니, 메모리초과가 발생하였다.
• String을 자르고 다시 붙이는 과정에서, 이런 일이 발생한다고 생각해서, String을 char단위로 쪼개서 연산하기로 하였다.
• 입력받은 문자열을 스택에 한자리씩 넣으면서, 지금 문자가 문자열2의 끝자리와 일치하는지 확인한다.
• 끝자리가 일치하면, 한 자리씩 앞으로 가며 문자열이 같은지 확인하고, 전부 같다면 그 길이만큼의 문자열을 스택에서 지운다.
  • 이렇게 하면, 지운 후 새로 생긴 문자열에서 문자열2가 생성되는 것을 한번에 발견할 수 있다.
• 이후에 스택에서 문자열을 꺼내고, 역순으로 출력한다.

전체 코드

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

public class BJ9935_물자열폭발 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		char[] ini = br.readLine().toCharArray();
		char[] ref = br.readLine().toCharArray();
		Stack<Character> stk = new Stack<>();
		
		int ilen = ini.length;
		int reflen = ref.length;
		for(int i = 0; i < ilen; i++) {
			stk.add(ini[i]);
			
//			System.out.println("사이클 시작 : " + stk.toString());
			
			if(ini[i] == ref[reflen-1]) {
				Stack<Character> tmpstk = new Stack<>();
				int loc = reflen;
				
				char a;
				do {
					loc--;
					if(loc >= 0 && stk.size() > 0) {
						a = stk.pop();
						tmpstk.add(a);						
					}
					else break;
					
				} while(loc >= 0 && a == ref[loc]);
				
				
				// 여기 오면 통과
				if(loc < 0) {
//					System.out.println("성공");
					continue;
				}
				// 여기 오면 실패
				else {
//					System.out.println("실패");
					while(!tmpstk.isEmpty())
						stk.add(tmpstk.pop());
				}
			}
//			System.out.println("사이클 끝 : " + stk.toString());
		}
		// 연산 끝.
		
		if(stk.isEmpty()) System.out.print("FRULA");
		else {
			StringBuilder sb = new StringBuilder();
			while(!stk.isEmpty()) sb.append(stk.pop());
			System.out.print(sb.reverse());
		}
	}
}

PS

당연히 통과 실패한 꼼수 코드…

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

public class BJ9935_물자열폭발 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		String ini = br.readLine();
		String ref = br.readLine();
		
		int lena, lenb = 0;
		do {
			lena = ini.length();
			
			ini = ini.replaceAll(ref, "");
            
			lenb = ini.length();
		} while(lena != lenb);
		
		if(ini.equals("")) System.out.print("FRULA");
		else	System.out.println(ini);
	}
}