SWEA 25838. 여우 줄이기

문자열이 주어질 때, 부분 문자열fox를 제거하여 길이가 최소가 되게 할 때의 길이를 구하는 문제이다.

 

처음에는 StringBuilder의 indexOf, delete를 이용하여 해결하려 했으나 문자열의 길이가 200000까지 될 수 있어 시간초과가 발생하였다.

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

public class Solution {
	private static String targetStr = "fox";
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int tc = Integer.parseInt(br.readLine());
		StringBuilder sb = new StringBuilder();
		while(tc-- > 0) {
			int length = Integer.parseInt(br.readLine());
			StringBuilder word = new StringBuilder(br.readLine());
			while(word.indexOf(targetStr) != -1) {
				int index = word.indexOf(targetStr);
				word.delete(index, index+3);
			}
			sb.append(word.length()).append('\n');
		}
		br.close();
		System.out.print(sb);
	}
}

 

 

이를 해결하기 위해 O(N)으로 풀 수 있는 자료구조 스택을 적용하여 문자열의 문자를 스택에 넣으면서 높이가 3 이상일 때, top-3, top-2, top-1이 각각 f, o, x 라면 해당 문자들을 스택에서 제거해 나가며, 최종 높이가 최종 문자열의 길이가 된다. 이렇게 하면 시간 초과 없이 fox를 문자열에서 제거할 수 있다. 또한, 실제 자바의 스택은 push, pop 밖에 없으므로 간단하게 char[]로 스택을 구현하였다.

int length = Integer.parseInt(br.readLine());
String word = br.readLine();
char[] stack = new char[length];
int top = 0;

for (int i = 0; i < length; i++) {
    stack[top++] = word.charAt(i);
    if (top >= 3 && stack[top-3] == 'f' && stack[top-2] == 'o' && stack[top-1] == 'x') {
        top -= 3;
    }
}
            
sb.append(top).append('\n');

 

 

결과 코드는 다음과 같다.

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

public class Solution {
	
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int tc = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        while(tc-- > 0) {
            int length = Integer.parseInt(br.readLine());
            String word = br.readLine();
            char[] stack = new char[length];
            int top = 0;
            
            for (int i = 0; i < length; i++) {
                stack[top++] = word.charAt(i);
                if (top >= 3 && stack[top-3] == 'f' && stack[top-2] == 'o' && stack[top-1] == 'x') {
                    top -= 3;
                }
            }
            
            sb.append(top).append('\n');
        }
        br.close();
        System.out.print(sb);
    }
}