글 읽기 - 어디서 시간초과가 날까요...

s48011 7년 전 0

첫 주석은 막연히 String과 StringBuilder를 이용해서 구현했으나, 시간초과.

원인을 append, reverse, toString 과정때문이라고 생각하고,

스택 2개를 이용해서 다시 구현했습니다. 그래도 또 시간초과가 나네요....

올바른 구현법을 아시거나, 제 코드에서 수정해야 될 부분을 아시면 알려주세요..

import java.util.*;
public class Censorship {

	/*
	static String a, t;

	public static String censor(String ans){
		if(!ans.contains(a)){
			return ans;
		}
		else{
			if(ans.contains(a)){
				ans = ans.replaceFirst(a, "");
			}
			StringBuilder a_tmp = new StringBuilder();
			StringBuilder t_tmp = new StringBuilder();
			t_tmp.append(ans);
			t_tmp = t_tmp.reverse();
			a_tmp.append(a);
			a_tmp = a_tmp.reverse();
			ans = t_tmp.toString();
			a = a_tmp.toString();
			if(ans.contains(a)){
				ans = ans.replaceFirst(a, "");
			}
			t_tmp.delete(0, t_tmp.length());
			a_tmp.delete(0, a_tmp.length());

			t_tmp.append(ans);
			t_tmp = t_tmp.reverse();
			a_tmp.append(a);
			a_tmp = a_tmp.reverse();

			ans = t_tmp.toString();
			a = a_tmp.toString();

			return censor(ans);
		}
	}

	public static void main(String[] args){
		Scanner read = new Scanner(System.in);
		String ans = "";

		a = read.nextLine();
		t = read.nextLine();
		ans = t;
		if(!t.contains(a)){
			System.out.println(ans);
		}
		else
			System.out.println(censor(ans));
	}*/


	static Stack<Character> s1 = new Stack<>();
	static Stack<Character> s2 = new Stack<>();

	public static void main(String[] args){
		Scanner read = new Scanner(System.in);

		String find, all;
		find = read.nextLine();
		all = read.nextLine();

		int check1 = 0, check2 = 0;
		while(all.contains(find)){
			int all_len = all.length();
			int j = 0;
			String ans = "";

            /* 첫 번째 매칭 부분 찾기 전까지 s1에 push */
			for(int i = 0; i < all_len-3; i++){
				if(all.charAt(i) == find.charAt(j) && all.charAt(i+1) == find.charAt(j+1) && all.charAt(i+2) == find.charAt(j+2)){
					check1 = i;
					break;
				}
				else{
					s1.push(all.charAt(i));
				}
			}

            /* 뒤에서부터 첫 번째 매칭 찾기 전까지 push */
			j = 2;
			for(int i = all_len - 1; i >= 2; i--){
				if(all.charAt(i) == find.charAt(j) && all.charAt(i-1) == find.charAt(j-1) && all.charAt(i-2) == find.charAt(j-2)){
					check2 = i;
					break;
				}
				else{
					s2.push(all.charAt(i));
				}
			}

            /* 처음부터 첫 번째, 뒤부터 첫 번째 사이의 문자 push */
			for(int i = check1 + 3; i < check2 - 2; i++){
				s1.push(all.charAt(i));
			}
            /* s1으로 몰아주고 */
			while(!s2.isEmpty()){
				s1.push(s2.pop());
			}
			/* 문자열 뒤집기위해 s2로 몰아주고 */
			while(!s1.isEmpty()){
				s2.push(s1.pop());
			}
			/* ans에 담기 */
			while(!s2.isEmpty()){
				ans += s2.pop();
			}
			
			all = ans;

		}
		System.out.println(all);
	}
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

어디서 시간초과가 날까요...

s48011 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말