인프런 커뮤니티 질문&답변

안녕하세요 선생님 강의 너무 잘 듣고 있습니다.

다름이 아니라 9.동전교환(DFS-Cut Edge Tech) 문제에 대해서 궁금한 점이 있어서 질문 올립니다.

강의 마지막 부분에서,

if(L>answer) return;

코드를 추가하여 불필요한 연산을 차단할 수 있다고 말씀해주셨는데,

동전의 최소 개수를 구하는 문제이니 만약 arr배열을 내림차순으로 미리 정렬하면 큰 단위의 동전부터 거슬러주게 되니 연산을 훨씬 더 줄일 수 있는 게 아닌가 하는 생각이 들었습니다. 이 문제의 경우도 5원짜리 3개인 경우가 바로 나오니 딱 한 번의 경우로 답을 구하여 연산이 더 빨라질 수 있지 않나요?

            function solution(M, arr){

                let answer=Number.MAX_SAFE_INTEGER;

                arr.sort((a,b)=>b-a);

                function DFS(L, sum){

                    if(sum>M) return;

                    if(L>answer) return;

                    if(sum===M){

                        console.log(L, sum);

                        answer=Math.min(answer, L);

                    } else {

                        for(let i=0; i<arr.length; i++){

                            DFS(L+1, sum+arr[i]);

                        }

                    }

                }

                DFS(0, 0);

                return answer;

            }

다만 궁금한 것은,

arr.sort((a,b)=>b-a); 를 추가했을 때 sort 함수를 사용하면 선생님이 하신 방법보다 연산 시간이 더 오래 걸리는지가 궁금합니다.

횟수로는 확실히 줄어드는 것 같아서요.

감사합니다.