졸업선물 문제 클래스 이용해서 풀었습니다 !
자바스크립트 알고리즘 문제풀이 입문(코딩테스트 대비)
완전 탐색 문제는 어렵네요 강의 보기 전에 하나씩 풀어보는데 졸업선물 문제는 기억에 남아서 올려봅니다. 그리고 강의도 재밌고 효율적으로 생각하는 방식을 잘 알려주시는 거 같습니다. < script > function solution ( m , product ){ class Product { constructor ( product = []){ this . _product = product ; } get price (){ return this . _product [ 0 ]; } get fare (){ return this . _product [ 1 ]; } disCountCost (){ return this . price / 2 + this . fare ; } cost (){ return this . price + this . fare ; } } class Products { constructor ( products = []) { this . _products = products ; } get commodities (){ return this . _products ; } get numOfProducts (){ return this . commodities . length ; } map ( transform ){ return new Products ( transform ( this . commodities )); } totalCost (){ return this . commodities . map ( product => product . cost ()). reduce (( sum , v ) => sum + v , 0 ); } } function possibleCost ( products ){ return products . commodities . map (( v , i ) => [ v , products . map ( makeDrop ( i ))]) . map (([ v , products ]) => v . disCountCost () + products . totalCost ()) . reduce (( minCost , current ) => Math . min ( minCost , current )); } function makeChildren ( products ){ const total = products . numOfProducts ; return total > 1 ? products . commodities . map (( _ , idx ) => products . map ( makeDrop ( idx ))) : [ products ]; } function makeGeneration ( depth , products ){ if ( depth === 0 ) return [ products ]; return makeChildren ( products ) . map ( sub => makeGeneration ( depth - 1 , sub )) . flat (); } const makeDrop = i => arr => arr . slice ( 0 , i ). concat ( arr . slice ( i + 1 )); const commos = new Products ( product . map ( commo => new Product ( commo ))); let limit = commos . numOfProducts ; for ( let i = 0 ; i < limit ; i ++){ if ( makeGeneration ( i , commos ) . filter ( prod => possibleCost ( prod ) <= m ) . length > 0 ) { return limit - i ; } } } let arr =[[ 10 , 3 ], [ 6 , 6 ], [ 2 , 2 ], [ 4 , 3 ], [ 4 , 5 ]]; console . log ( solution ( 28 , arr )); </ script >
- 객체지향
- 졸업선물





