글 읽기 - 시간 초과 및 접근 방법 질문 드립니다.

nogune 5년 전 0

문제에 나온 순서 대로 구현을 하였는데, 시간 초과가 뜹니다.

구현 방법은

1. 왼쪽 탐색 ( l < r) 후 찾은 문자열 제거

2. 오른쪽 탐색 ( l <=r ) 후 찾은 문자열 제거

3. 합친 새로운 문자열 = 왼쪽문자열 + 미탐색 구간 + 오른쪽 문자열

4. 왼쪽 오른쪽 둘 다 없을 시 종료 (1번 찾을 떄 찾는 문자열이 없는 경우 끝까지 탐색하므로 합친 문자열을 다시 탐색 하지 않아도 됨)

5. 합친 문자열 출력

import java.util.Arrays;
import java.util.Scanner;

public class Main {
/*
 * 
aba
ababacccababa
=> bacccab

abc
fabaabcbcabccd
=>fd

abc
abababcccc
=>c

 * */
	
	static char[] word;
	static char[] text;
	static int word_size;
	static int text_size;
	static char [] now_left;
	static char [] now_right;
	
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		
		word = sc.next().toCharArray();
		word_size = word.length;	
		text = sc.next().toCharArray();
		text_size = text.length;
		
		
		char[] left = new char[text_size];
		char[] right = new char[text_size];
		
		
		now_left = new char[word_size];
		now_right = new char[word_size];
		
		int l = 0; // text 왼쪽 참고 위치
		int i = 0; // 왼쪽 스택의 현재 위치
		
		int r = text_size-1; // text 오른쪽 참고 위치
		int j = 0; // 오른쪽 스택의 현재 위치
		
		boolean left_result = false;
		boolean right_result = false;
		
		// 왼쪽에서 지우기
		while(true) {
			
			while(l<r) {
				left[i] = text[l];
				char [] tmp = new char[word_size];
				
				System.arraycopy(now_left, 1, tmp, 0, word_size-1);
				tmp[word_size-1] = text[l];
				System.arraycopy(tmp, 0, now_left, 0, word_size);
				
				if(Arrays.equals(now_left, word)){
					
					int ii=0;
					while(ii<word_size) {
						if(i-ii>=0) {
							left[i-ii]='E';	
						}
						ii++;
					}
					
					i = i-word_size;
					
					ii=0;
					while(ii<word_size-1) {
						if(i-ii>= 0) {
							now_left[word_size-1-ii] = left[i-ii];
						} else {
							now_left[word_size-1-ii] = 'E';
						}
						ii++;
					}
					l++;
					i++;
					left_result = true;
					break;
				}
				l++;
				i++;
			}
			
			while(l<=r) {
				right[j] = text[r];
				char [] tmp = new char[word_size];
				
				System.arraycopy(now_right, 0, tmp, 1, word_size-1);
				tmp[0] = text[r]; 
				System.arraycopy(tmp, 0, now_right, 0, word_size);
				
				if(Arrays.equals(now_right, word)){
					
					int jj=0;
					while(jj<word_size) {
						if(j-jj>=0) {
							right[j-jj]='E';	
						}
						jj++;
					}
					
					j = j-word_size;
					
					jj = 0;
					while(jj<word_size-1) {
						if(j-jj>=0) {
							now_right[jj] = right[j-jj];
						} else {
							now_right[jj] = 'E';
						}
						jj++;
					}
					r--;
					j++;
					right_result = true;
					break;
				}
				r--;
				j++;
			}
			
			text_size = i + j + r - l + 1;
			 
			// 합치기 -안 탐색한 구간
			while(l<=r) {			
				left[i++] = text[l++]; 
			}
			
            // 합치기 - 오른쪽 스택
			while(j>0) {
				left[i++] = right[--j];
			}
			
			text = new char[text_size];
			System.arraycopy(left, 0, text, 0, text_size);

			// 왼쪽 오른 쪽 둘 다 없는 경우 종료
			if(!left_result && !right_result) {
				System.out.println(String.copyValueOf(text));
				break;
			}
			
			// 초기화
			
			left = new char[text_size];
			right = new char[text_size];
			
			
			now_left = new char[word_size];
			now_right = new char[word_size];
			
			l = 0; // text 왼쪽 참고 위치
			i = 0; // 왼쪽 스택의 현재 위치
			
			r = text_size-1; // text 오른쪽 참고 위치
			j = 0; // 오른쪽 스택의 현재 위치
			
			left_result = false;
			right_result = false;
			
		}
		
//		System.out.println(String.copyValueOf(left, 0, i));
	}
}

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

문제

문제

출처

ICPC

시간 초과 및 접근 방법 질문 드립니다.

nogune 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말