bbayu   2년 전

원래 이문제는 

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

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


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

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

chogahui05   2년 전

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   2년 전

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

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


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

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

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


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

bbayu   2년 전

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

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

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

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

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

chogahui05   2년 전

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

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

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


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

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

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

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

bbayu   2년 전

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

어쨋던 해결했으니깐요!

그나저나 감사드립니다!

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

좋은 주말 보내세요

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