글 읽기 - 자바 문자열에 관한 연산 속도 질문드릴게요

bbayu 5년 전 0

원래 이문제는

알파벳 a~z까지 각각 배운다. 배우지 않는다. 로 나뉘어 2^26의 시간복잡도를 갖는 조건으로 비트연산을 수행하여 풀더라고요.

제가 아래와 같이 풀이한 방식은 배워야 하는 알파벳 중에서 조합을 이용하여 풀었는데요. 왜 시간초과가 나는지 잘 모르겠습니다..

아래 소스코드에 ★ 표시와 함께 질문을 달아놓았습니다.

해당 부분에서 궁금한 사항이 생겼는데 답해주시면 감사하겠습니다 ! ^^

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

public class Main {
	public static int N;
	public static int K;
	public static int R;
	public static String[] wordlist;
	public static ArrayList<Integer> alphabetlist;
	public static int com[];
	public static int MAX=0;
	public static int visited[] = new int[26];

	public static void main(String[] args) throws IOException {
		BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));

		String a[] = bufferedReader.readLine().split(" ");

		N = Integer.parseInt(a[0]);
		K = Integer.parseInt(a[1]);
		wordlist = new String[N];
		alphabetlist = new ArrayList<>();

		if (K <= 4) {
			System.out.println(0);
			return;
		}
		; // R은 조합에서 뽑는 개수
		
		for (int i = 0; i < N; i++) {
			
			wordlist[i] = bufferedReader.readLine();
			for (int j = 0; j < wordlist[i].length(); j++) {
				int alphabet = wordlist[i].charAt(j);

				if (alphabet == 'a') {
					wordlist[i] = wordlist[i].replaceAll("a", ""); j=-1; continue;}
				if (alphabet == 'n') {
					wordlist[i] = wordlist[i].replaceAll("n", ""); j=-1; continue;}
				if (alphabet == 't') {
					wordlist[i] = wordlist[i].replaceAll("t", ""); j=-1; continue;}
				if (alphabet == 'i') {
					wordlist[i] = wordlist[i].replaceAll("i", ""); j=-1; continue;}
				if (alphabet == 'c') {
					wordlist[i] = wordlist[i].replaceAll("c", ""); j=-1; continue;}

				if(visited[alphabet-'a'] != 1) {
					alphabetlist.add(alphabet); // a,n,t,i,c를 제외한 알파벳의 
                                                // int 타입이 들어가 있다.
					visited[alphabet-'a'] = 1;
				}
				

			}

		}

		if(K==5) {
			int count = 0;
			for (int i = 0; i < N; i++) {
				if(wordlist[i].length() == 0) {
					count++;
				}
			}
			
			MAX = Math.max(MAX, count);
			System.out.println(MAX);
			return;
		}
		
	
		R = K-5;
		
		if(R>alphabetlist.size()) {
			System.out.println(N);
			return;
		}
		
		
		com = new int[alphabetlist.size()];
		dfs(wordlist,0,0);
		
		System.out.println(MAX);
		
	}

	private static void dfs(String wordlist1[], int index, int depth) {// 조합을 실행하는 dfs
		// TODO Auto-generated method stub
		
		if(depth == R) {
			int count = 0;
			for (int i = 0; i < N; i++) {
				
				if(wordlist1[i].equals("")) {    // ★ 1. 문자열을 비교하는 과정도 속도영향이 큰가요?
					count++;
				}
			}
			
			MAX = Math.max(MAX, count);
			
			return;
		}
		
		
		String a[] = copyString(wordlist1);
		
		for (int i = index; i < alphabetlist.size(); i++) { // 배울 알파벳은 선정하는 단계
			for (int j = 0; j < N; j++) {
				wordlist1[j] = 
           wordlist1[j].replaceAll(String.valueOf((char)alphabetlist.get(i).intValue()), "");	// 알파벳 배움
            }    // ★ 2. ↑ replaceALL이라는 메소드를 쓰는것은 속도에 매우 큰 영향을 끼치나요?
			
			
				dfs(wordlist1, i+1, depth+1);
			
			
			
			wordlist1 = copyString(a);
			
			
		}
		
		
		
	}

	private static String[] copyString(String[] wordlist1) {
		// TODO Auto-generated method stub
		String a[] = new String[N];
		for (int i = 0; i < N; i++) {
			a[i] = wordlist1[i];
		}
		return a;
	}

	
	
}

chogahui05 5년 전 0

2^26 >> 2^21이므로

2^21로 푸는 게 이득입니다. 2^26 = 6700만 정도 되네요. 2^21 = 209만 이지요. 32배나 차이납니다.

2^26으로 푸시려면, sub task에 대해서 O(1)이 보장되어야 하는데요.

wordlist1[i].equals("");

이건 별 영향을 끼치지 않을 겁니다. ""의 길이가 0이기 때문입니다.

문제는

wordlist1[j].replaceAll(String.valueOf((char)alphabetlist.get(i).intValue()), ""); 인데.

chogahui05 5년 전 0

replaceAll이라는 친구가 제 기억으로는 1번째 인자에 regex가 들어올 거고

2번째 인자에 바꿀 녀석으로 들어올 겁니다.

그렇다면. regex가 맞는지 판단하는 시간 T가 포함이 될 거고요.

그걸 각각의 문자, 혹은 부분 문자열에 대해서 판단해야 하니까. 최소한 O(len*T)는 넘겠네요. O(1)에 풀어야 하는 걸.

학생들은 그 K개의 글자로만 이루어진 단어만을 읽을 수 있다. 김지민은 어떤 K개의 글자를 가르쳐야 학생들이 읽을 수 있는 단어의 개수가 최대가 되는지 고민에 빠졌다.

고 하니까, K-5개의 글자를 미리 정해놓고 탐색해 보세요.

bbayu 5년 전 1

제 코드도 최대 21가지의 경우의 수를 놓고 따지도록 작성하였습니다. (꼭 배워야하는 a,t,i,c,n 제외)

계속 생각해보았는데요. 111~114 줄이 문제였습니다.

replaceall 메소드의 문제라기보다. N번 반복하는 for문에 문제가 있었습니다.

dfs 1번당 계산해야하는 것이 111~114 줄의 for문으로 인해 엄청나게 시간 효율성이 떨어지네요.

그래서 단어들을 비트연산으로 비교하니 풀렸습니다 ^^ 감사합니다.

chogahui05 5년 전 1

함수 자체 복잡도도 무시 못했을 거에유. 그와는 별개로

bbayu님 말씀대로 N번 반복까지 하니까.. replaceAll과는 별개로.

최악의 경우 계속 N번 비교할 거니.. ㄷㄷ;;

java에서 debug 돌려보셔서 replaceAll은 뜯어보시면 공부 많이 되실 거에요.

bit 연산의 특성을 이용하는 것 중 하나가.

https://www.acmicpc.net/proble...

이 친구가 있어요. 마찬가지 방식으로 접근하면 풀려요.

bbayu 5년 전 0

최악의 경우에는 count해보니 1억번을 그냥 넘어가더군요.....

어쨋던 해결했으니깐요!

그나저나 감사드립니다!

문제 추천해주신것은 시간될때 풀어보도록 할게요.

좋은 주말 보내세요

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

문제

문제

출처

ICPC

자바 문자열에 관한 연산 속도 질문드릴게요

bbayu 5년 전 0

chogahui05 5년 전 0

chogahui05 5년 전 0

bbayu 5년 전 1

chogahui05 5년 전 1

bbayu 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말