aquaris201   3년 전

* words : 단어들을 담는 길이 N의 배열

* alphaRes : alphaList에서 조합으로 K-5개를 뽑아서 만든 단어 배열 (가진 알파벳의 인덱스가 1, 가지지 못한 알파벳의 인덱스 0)

* alphaList : N개의 단어들에서 a, n, t, i, c 을 제외한 단어를 담은 리스트

* visited : alphaList에서 단어를 뽑을 때 방문 여부 확인 (a ; 인덱스0 부터 z ; 인덱스 25)

K가 5개 미만이면 무조건 0 출력하게 했고, 

5이상인 경우 a,n,t,i,c를 무조건 가집니다. (line33 - line 37)

처음에 단어를 입력 받을 때마다 anta, tica를 제외한 나머지 단어를 alphaList에 담습니다. (중복제외)

이후에 alphaList의 크기가 k-5 이하이면 모든 단어를 다 배울 수 있으므로 N 출력합니다.

아닌 경우 조합을 통해 alphaList에서 K-5개를 뽑아서 alphaRes에 반영한 뒤, words들의 단어들을 비교해서 배울 수 있는 단어 수를 정하고 최대값과 비교해 최대값을 결정합니다.


재귀나 단어의 반복에서는 최대한 반복수를 줄였는데도 불구하고 계속 시간 초과네요.

도움 부탁드립니다!

slah007   3년 전

CheckWord가 N^2이고 getSolve가 2^K라면 50^2*2^21 = 50억으로 반복 횟수가 너무 많습니다.

checkWord를 N+K번의 반복만으로 어떻게 할 수 있을까요?

aquaris201   3년 전

답변 감사합니다!

계속 생각 중인데 아직은 해답을 못찾았네요.

다른 함수는 두고 checkWords만 수정해서 N+K 반복으로 만드는건가요..?

감이 너무 잡히지가 않습니다ㅠ... 죄송합니다.

slah007   3년 전

아 생각해보니까 2^21번을 전부 도는게 아니라서 아슬아슬하게 통과할 거 같기도 하네요.

약간 더 최적화하자면

1. 어차피 max는 전역변수이니 int checkWords() 대신에 void를 써보세요.

2. charAt(j) 대신 word[i][j]를 써보세요.

이런 식으로는 통과가 안되면 재귀함수 대신에 비트마스크를 사용해야 합니다. 비트마스크에 대해 찾아보세요.

slah007   3년 전

checkWords()의 시간복잡도 NK를 N으로 줄이는건 그냥 제 착각이었습니다. NK보다 줄일 수는 있지만 너무 복잡해요.

aquaris201   3년 전

자세한 답변 정말 감사합니다!

한 번 생각해서 다시 풀어보도록 하겠습니다 좋은 밤 되십쇼 : )

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