글 읽기 - 문자열 탐색문제 시간초과에 대한 질문입니다.

kdh9520 9년 전 0

단순히 스트링을 처음에 다 만들어서 했더니 시간초과가나서,

길이가 모자랄 때 마다 찾는배열의 길이를 조금 씩 늘리면서 하는 방식으로 약간 더 동적으로 바꾸었으나 똑같이 시간초과가 뜨네요.

어떤방식으로 풀어야할지 계속 고민을해도 좋은 방법이 생각이 나질 않네요...

import java.util.*;
import java.io.*;

class Main {
	private static int l, point, add;
	private static String targetS, searchingS;

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

		int input = keyboard.nextInt();
		searchingS = "1";
		add = 2;// 늘릴때 포인터
		targetS = String.valueOf(input);
		l = targetS.length();// 타겟길이
		point = 0;// String내부에서 찾는포인트
		while (true) {
			makeS();
			if (searchingS.substring(point, point + l).equals(targetS)) {
				System.out.println(point + 1);
				return;
			}
			point++;
		}

	}

	private static void makeS() {
		while (searchingS.length() - point < l) {
			searchingS = searchingS.concat(String.valueOf(add++));
		}

	}
}

yukariko 9년 전 1

저는 질문자께서 처음 푸신 방법대로

미리 스트링을 만들어놓고 문자열 검색 알고리즘을 이용해 해결했습니다.

input이 최대일때의 길이를 생각해서 미리 버퍼를 잡아놓고 스트링을 만들면 좀 더 빨라지지 않을까 싶네요.

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

문제

문제

출처

ICPC

문자열 탐색문제 시간초과에 대한 질문입니다.

kdh9520 9년 전 0

yukariko 9년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말