글 읽기 - 왜이렇게 오래걸릴까요?

beehive2838 1년 전 0

속도가 약 2700ms정도 나옵니다

의도는 입력되는 문자열 길이를 주소삼아서

다음 입력되는 비교할 문자들을 그 주소로 바로 찾아가서 비교하게 했는데(이 방식이 느린건지..)

하나하나 일일이 다 비교해서 찾는 것도 아닌데

어떤 코드가 효율적인지 아니면 비효율적인지도 잘 모르겠고,

입력 방식에 문제가 있는지, 아니면 비교하는 과정에 문제가 있는지

의도한 대로 짜지 못한 건지 아니면 뭔가 잘못 들어간 코드가 있는지 모르겠습니다 ㅠ,ㅠ

import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		st = new StringTokenizer(br.readLine(), " ");
		int N = Integer.parseInt(st.nextToken()), M = Integer.parseInt(st.nextToken());
		
		String[][] str = new String[501][Math.max(N, M)]; // 500자
		int[] count = new int[501];
		
		while(N--> 0) {
			
			String input = br.readLine();
			str[input.length()][count[input.length()]] = input;
			count[input.length()]++;
			
		}
		
		int cnt = 0;
		while(M--> 0) {
			
			String input = br.readLine();
			
			if(count[input.length()] == 0) continue;
			for(int i = 0; i < count[input.length()]; i++) {
				
				if(input.equals(str[input.length()][i])) cnt++;
				
			}
			
		}
		System.out.print(cnt);
		
	}
}

yup0927 1년 전 0

제가 이해를 맞게 했는지는 모르겠습니다만,

입력으로 주어진 문자열의 길이가 다 동일하고 그 문자열들끼리 뒤에 몇 글자만 서로 다르다면

(예시: aa..aa, aa..ab, aa..ac)

그리고 찾으려고 하는 문자열 역시 길이가 동일하고 뒤 몇 글자만 다르다면

한 번 찾으려고 할 때 최대 O(N)의 시간이 걸릴 거고, 비교하는 과정도 O(|S|)로 문자열의 길이에 비례하므로

최악의 경우에는 문자열을 찾으려고 할 때마다 O(500N)에 육박하는 시간이 걸릴 것으로 보입니다.

(문제에서 문자열의 최대 길이가 500이라고 가정했으므로)

즉, 해당 코드의 최악의 경우 실행 시간은 O(500NM) 좀 안 되게 나올 것 같습니다.

(의도적으로 최대 길이 문자열만 주어지고, 찾으려는 문자열 역시 최대 길이이며 존재하지 않을 경우에)

시간을 줄이기 위해서는 해싱을 통해서 처리하셔야 할 것 같습니다.

HashMap()에 대해 찾아보심이 좋을 것 같습니다.

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