글 읽기 - 시간 초과 문제 도와주시면 감사하겠습니다.

shfksekdrms2 6년 전 0

아래와 같이 먼저 move 배열에 값을 넣어서 틀린 위치만큼 move 배열에 있는 값만큼 이동시키면서 존재 하는 값이 있는지 확인하는 로직입니다.

하지만, 3~6 % 대에서 시간 초과가 발생하네요...

어디를 손봐야할지 감이 안옵니다!! 도와주시면 감사하겠습니다.

import java.util.LinkedList;
import java.util.Scanner;

//1786
public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		char[] arr = sc.nextLine().toCharArray();
		char[] findArr = sc.nextLine().toCharArray();
		int[] move = new int[findArr.length+1];
		int i, j;
		String str = "";
		String prefix = "";
		String suffix = "";
		move[0] = -1;
		for(i=0; i<findArr.length; i++){
			str += findArr[i];
			prefix = "";
			suffix = "";
			for(j=0; j<str.length()/2; j++){
				prefix += str.charAt(j);
				suffix = str.charAt(str.length()-j-1) + suffix;
				if(prefix.equals(suffix)){
					//move 배열에 prefix와 suffix의 최대 경계값에 대한 길이 입력
					move[i+1] = prefix.length();
					break;
				}
			}
		}
		boolean findStr = true;
		LinkedList<Integer> list = new LinkedList<>();
		for(i=0; i<arr.length-findArr.length+1;){
			findStr = true;
			for(j=0; j<findArr.length; j++){
				if(arr[i+j] != findArr[j]){
					//틀린 경우 위치 이동
					i += j-move[j];
					findStr = false;
					break;
				}
			}
			if(findStr == true){
				//다맞은 경우에 1칸 이동
				list.add(i+1);
				//맞은 경우 위치 이동
				i += j-move[j];
			}
		}
		System.out.println(list.size());
		for(i=0; i<list.size(); i++){
			System.out.print(list.get(i)+" ");
		}
		
	}
}

jh05013 6년 전 1

전처리 과정이 O(m)인 것 같지 않습니다. KMP 알고리즘을 찾아보세요.

shfksekdrms2 6년 전 0

이거 KMP 알고리즘인데요...??? 어느 부분에서 아니라고 생각하는지 잘이해가안되네요

분명 move 배열에 prefix와 suffix 의 최소 길이 만큼 이동할 수 있게 저장해놓았고

그이후에 계속 확인하고 틀릴 경우 해당 move의 값만큼 이동해서 다시 비교하는 로직입니다.

정확히 똑같지는 않더라도 방법은 맞다고 생각하는데요...

chogahui05 6년 전 1

하나 궁금한 게 있는데요.

String에 왜 +연산자를 쓰신 건가요? 이거 시간 복잡도도 그렇고 공간 복잡도도 엄청날텐데요..

shfksekdrms2 6년 전 0

StringBuffer로 append 로 변경하고 다시 한번 확인해 보겠습니다.
의견 감사합니다 ㅎㅎ

shfksekdrms2 6년 전 0

아래와 같이 String으로 구성되어 있는 것들을 모두 StringBuffer로 변경하였는데도 시간 초과가 발생하네요... ㅜㅜ

import java.util.LinkedList;
import java.util.Scanner;

//1786
public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		char[] arr = sc.nextLine().toCharArray();
		char[] findArr = sc.nextLine().toCharArray();
		int[] move = new int[findArr.length+1];
		int i, j;
		StringBuffer str = new StringBuffer("");
		StringBuffer prefix;
		StringBuffer suffix;
		move[0] = -1;
		for(i=0; i<findArr.length; i++){
			str = new StringBuffer(str).append(findArr[i]);
			prefix = new StringBuffer();
			suffix = new StringBuffer();
			for(j=0; j<str.length()/2; j++){
				prefix = new StringBuffer(prefix).append(str.charAt(j));
				suffix = new StringBuffer(suffix).insert(0, str.charAt(str.length()-j-1));

				if(prefix.toString().equals(suffix.toString())){
					//move 배열에 prefix와 suffix의 최대 경계값에 대한 길이 입력
					move[i+1] = prefix.length();
					break;
				}
			}
		}
		boolean findStr = true;
		LinkedList<Integer> list = new LinkedList<>();
		for(i=0; i<arr.length-findArr.length+1;){
			findStr = true;
			for(j=0; j<findArr.length; j++){
				if(arr[i+j] != findArr[j]){
					//틀린 경우 위치 이동
					i += j-move[j];
					findStr = false;
					break;
				}
			}
			if(findStr == true){
				list.add(i+1);
				//맞은 경우 위치 이동
				i += j-move[j];
			}
		}
		System.out.println(list.size());
		for(i=0; i<list.size(); i++){
			System.out.print(list.get(i)+" ");
		}
		
	}
}

jwvg0425 6년 전 2

대충 비슷하다고 생각하지 마시고 정확히 공부하신 다음에 구현해보시는게 좋을 것 같습니다. 작성하신 코드에서 테이블을 구성하는 전처리 과정의 시간 복잡도가 정말로 KMP 알고리즘이랑 동일한가요? kmp 알고리즘에서 테이블 만들 때 정말로 매번 prefix와 suffix 전체를 일일히 비교를 하던가요? 그 문자열 비교의 시간복잡도가 얼마나 될까요?

chogahui05 6년 전 1

kmp는 둘째 치고라도

string 객체와 stringbuffer, stringbuilder 객체에 대한 이해가 필요할 거 같네요.

그냥 간단하게 예제 하나 찾아서 적용시켜 보시고 코딩해 보세요.. 그러면 더 수월해요..

굳이 append 시킬 때 new로 할당할 필요 없을텐데.. 21번째에서 22번째 줄을 보세요..

생성자가 어떤 식으로 동작되는지는 모르겠지만.

prefix = new StringBuffer(prefix)

이 친구를 넘기면서 이전의 prefix는 쓰지 않잖아요. 쓰지 않는 prefix가 가비지 콜렉터에 의해서 수거라도 된다면 그나마 다행인데

수거가 안 되어버리면 그게 메모리 릭이에요. 루트에서 연결되어 있으니까 갈 수는 있는데 정작 안 써는다면 그야말로.. 최악인 거죠.

가비지 콜렉터도 꼭 검색해 보세요.

chogahui05 6년 전 1

주요 언어들 레퍼런스 찾는 연습을 꾸준히 하시는 게 좋아요.

제가 4학년이 되고 졸업반이 되었는데도 그게 (지금도) 잘 안 되어서 뼈저리게 후회하고 있어요.

그러니까 내가 처한 상황이 이러이러한데.

이런 걸 해결하기 위해서는 어떤 메서드를 써야 좋을지.. 기본적인 레퍼런스 사이트에서 검색을 해 보시고요.

시간 복잡도 분석도 해 보세요. 그러면 공부 많이 됩니다..

이전에 정규식? 같은.. 정확히는 dp로 푸는 문제가 나왔을 때

저는 regex 클래스를 써서 접근을 해 봤는데요. 시간초과가 나더라고요. 왜 나지?

이러면서 공부해 보시라는 것이죠..

shfksekdrms2 6년 전 0

jwvg0425 님
테이블을 구할때 O(nm)이 걸리는걸 생각하지 못했네요;; 감사합니다.

chogahui05님
문자열 처리를 하면서 시간 및 공간 복잡도가 증가한다는 사실 명심하겠습니다.
그래서 그냥 소스를 문자열 자체 비교가 아닌 인덱스 비교로 바꾸었습니다.

다들너무 나도 많은 도움 주셔서 감사합니다.
하여 아래와 같이 수정하였습니다.
그럼에도 불구하고 50% 에서 시간 초과가 발생하네요...ㅜㅜ

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

//1786
public class Main {
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();

		char[] arr =  br.readLine().toCharArray();
		char[] findArr = br.readLine().toCharArray();
		int[] move = new int[findArr.length];
		int i, j=0;
		for(i = 1; i< move.length; i++){ 
            //중간 부분 뛰어넘는 단계
			while(j > 0 && findArr[i] != findArr[j]){
				j = move[j-1];
			}
			if(findArr[i] == findArr[j]){
				move[i] = ++j; 
			}
		}
		j=0;
		LinkedList<Integer> list = new LinkedList<>();
		for(i=0; i<arr.length; i++){
            //중간 부분 뛰어넘는 단계
			while(j>0 && arr[i] != findArr[j]){
				j = move[j-1];
			}
			if(arr[i] == findArr[j]){ 
				if(j==findArr.length-1){ 
					list.add(i-findArr.length+2); 
					j = move[j]; 
				}else{ 
					j++; 
				} 
			}
		}

		System.out.println(list.size());
		for(i=0; i<list.size(); i++){
			System.out.print(list.get(i)+" ");
		}
		
	}
}

jh05013 6년 전 1

list.get(i)가 얼마나 걸리나요? 그걸 O(n)번 반복하면 어떻게 될까요?

내장함수의 시간복잡도 정도는 숙지합시다.

chogahui05 6년 전 1

시간 복잡도를 쉽게 알아볼 수 있는 방법이 있어요.

c나 java나 파이선이나 시간 측정함수 있을 거잖아요.

데이터 갯수를 순차적으로 증가시켜보면서 측정해 보는 것이지요. 그래도 모르시겠다면 찾아보셔도 되고요.

List 같은 경우에는 get 메서드의 시간 복잡도는 최악의 경우 O(n)이 걸려버립니다.

연속적이지 않거든요. 배열이야 charAt(i) 같은.

그러니까 i번째 원소를 꺼내오는 연산이 O(1)만에 되어버립니다. 그냥 기준점이 되는 base만 알면 되거든요.

Linked List는 그게 안 됩니다.

이게 계속 연결 되어 있는 포인터를 따라서 가야 됩니다.

그건 그렇다 치고.. 메모리 릭이라던지.. 가비지 같은 건 숙지하세요..

개인적으로 되게 답답한 건.

java는 가비지 콜렉터가 알아서 다 해주겠지~ 히힛. 이런 생각을 하시는 겁니다.

chogahui05 6년 전 1

이쪽에서 헤메시는 걸로 봐서는 1학년, 혹은 2학년 분이신 거 같은데요..

전 지금 와서야 찾고 있어도 잘 안 됩니다.. 안 찾아봐서요. 정말 끝까지 안 찾아지더군요.

나이가 먹을 만큼 먹었으니 머리도 안 돌아가더라고요. 그리고 습관 고치는 것도 어려워요. 이게 해 오던 게 있거든요.

맨 처음에 언어 같은 걸 배울 때 습관을 진짜 잘 들여놓으셔야 하는데.

제가 그러지 못했어요. 배우신 지 얼마 안 되셨다면.. 그렇게 늦지 않으셨으니까..

지금부터라도 코드도 정리 함 해 보시고.. 레퍼런스도 찾아보시고. 그런 습관을 가지시면 좋겠어요.

shfksekdrms2 6년 전 0

아 JAVA의 자료 구조 특성을 전혀 생각하지 않고 코드를 짜다보니 단순 출력에서 O(n^2)이라는 시간이 걸렸네요.. 전혀 생각지도 못했던 부분이네요...

그냥 편해서 썼던 부분이 이슈가 될줄은 생각지도 못했습니다...

Linkedlist 부분은 ArrayList 형식으로 바꾸어서 제출한 결과 정답으로 인식하네요...

오늘 도움을 주신 많은 분들께 감사의 인사를 드시며 앞으로도 많은 부탁드립니다.

이렇게 하나 배워갑니다. 고맙습니다.^^

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

문제

문제

출처

ICPC

시간 초과 문제 도와주시면 감사하겠습니다.

shfksekdrms2 6년 전 0

jh05013 6년 전 1

shfksekdrms2 6년 전 0

chogahui05 6년 전 1

shfksekdrms2 6년 전 0

shfksekdrms2 6년 전 0

jwvg0425 6년 전 2

chogahui05 6년 전 1

chogahui05 6년 전 1

shfksekdrms2 6년 전 0

jh05013 6년 전 1

chogahui05 6년 전 1

chogahui05 6년 전 1

shfksekdrms2 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말