bbayu   2년 전

조합을 이용하도록 dfs로 완전 탐색을 해보았는데요.

시간초과가 나는군요.. 어느 조건을 걸어줘야 신속하게 걸어줄 수 있나요?

이 문제의 정답을 보니 비트연산을 많이 사용하시던데요.

문자열 배열 그 자체로 재귀를 돌리는 부분에서 문제가 있는걸까요??

이런 문제들을 만날때 해결법을 빠르게 찾지 못하는 저의 능력.. 언제 실력이 늘 수 있을까요

sgckk   2년 전

제가 자바를 안해서 코드를 정확히 이해는 못했지만

이 문제는 모든 단어를 한번씩만 탐색해도 문제를 푸실 수 있습니다.

조합을 쓰셨다는게 어떤의미인지 잘모르겠네요

bbayu   2년 전

문제에서 antic 를 제외한 글자 중에서 만약 3가지의 글자를 추가적으로 배워야 모든 단어를 읽을 수 있다면

이 3가지의 글자중에서 k-5개를 배울 수 있는 모든 가지의 경우의 수를 계산합니다.

최대로 읽을 수 있는 단어 개수를 출력하도록 dfs를 구현하였습니다. 

테스트케이스 여러가지로 정답을 맞춰보면 알맞게 구현이 되어있다는 것을 알 수 있는데요.

시간초과라는 부분이 왜 발생하는건지 잘 모르겠네요.

다른 풀이방식들을 보면 각 알파벳을 배우는 경우, 배우지 않는 경우 총 2^26가지의 조합을 탐색하여서 비트연산으로 단어를 읽을 수 있는지 없는지를 탐색하더라고요.

이는 시간복잡도가 2^26인데도 불구하고 통과하는 반면에.

저의 방식은 딱 배워야하는 글자를 골라서 그 중에서 k-5개를 탐색하는데도 시간초과가 발생합니다.

비트연산을 안하고 문자열 그 자체로 계산을 해서 시간초과가 나는건지 궁금하네요~!

bbayu   2년 전

아.. 제가 구현방식은 조합을 이용하기 때문에 antic를 제외한 2^21 가지의 조합을 탐색하지만,

 각 dfs마다 소스코드 108라인~110라인에 해당하는 부분이 문제에서 주어지는 n번을 반복하게 됩니다.

n번은 최대 50으로 문제에서 설정되어 있으니..


50*2^21 은 1억을 초과하게 되네요. 


이런..!! dfs마다 문자열을 삭제하고 다음 단계로 문자열을 넘겨주는게 문제였군요. 

단순히 자바의 문자열 메소드가 문제가 아닌 것 같네요! 
 

sgckk   2년 전

문제 푸셨나요??

bbayu   2년 전

네 해결하였습니다! 

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