CheckWord가 N^2이고 getSolve가 2^K라면 50^2*2^21 = 50억으로 반복 횟수가 너무 많습니다.
checkWord를 N+K번의 반복만으로 어떻게 할 수 있을까요?
1062번 - 가르침
답변 감사합니다!
계속 생각 중인데 아직은 해답을 못찾았네요.
다른 함수는 두고 checkWords만 수정해서 N+K 반복으로 만드는건가요..?
감이 너무 잡히지가 않습니다ㅠ... 죄송합니다.
자세한 답변 정말 감사합니다!
한 번 생각해서 다시 풀어보도록 하겠습니다 좋은 밤 되십쇼 : )
댓글을 작성하려면 로그인해야 합니다.
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들의 단어들을 비교해서 배울 수 있는 단어 수를 정하고 최대값과 비교해 최대값을 결정합니다.
재귀나 단어의 반복에서는 최대한 반복수를 줄였는데도 불구하고 계속 시간 초과네요.
도움 부탁드립니다!