[프로그래머스] 메뉴 리뉴얼 (javascript)

하루종일 풀었다 휴

원래는 course 배열의 for문을 가장 바깥으로 하여 중첩 포문을 돌렸는데 시간 초과가 나서 

조합을 따로 구해주고 모든 조합이 구해진 후 최대값을 갱신해주는 방식으로 중첩 for문을 분리시켰다.

 

function solution(orders, course) {
    var answer = [];
    orders.sort((a,b)=>a.length-b.length); //크기 별로 정렬해놓는다.
    let dict={}; //조합의 결과가 들어갈 것이다. (문자열, 등장횟수)쌍
    
    function comb(idx, s,len, str, visited,start){ //조합을 돌린다.
    if(idx===len){ //기준 길이(course[i])
        str=str.split("").sort().join("");
        dict[str]=dict[str]?dict[str]+1:1; //등장한 적이 있다면 +1해준다.
        return;
    }
    for(let i=start;i<s.length;i+=1){
        if(visited[i])continue;
        visited[i]=true;
        comb(idx+1,s,len,str+s[i],visited,i+1);
        visited[i]=false;
    }

}
    // 조합 구하기, 각 문자열의 부분집합을 구하여 모든 조합의 등장 횟수를 구해준다.
        for(let j=0;j<orders.length;j+=1){//조합을 구하는 주문 문자열
            let visited=Array(orders[j].length).fill(false);
             for(let i=0;i<course.length;i+=1){
                if(orders[j].length<course[i])continue; // 만약 길이가 뽑으려는 수보다 작다면 pass
                comb(0,orders[j],course[i],"",visited,0); //일단 모든 조합을 구해 놓는다.
             }  
        }
        //조합을 key value 쌍의 배열로 변환
      let arr=Object.entries(dict);
      for(let i=0;i<course.length;i+=1){
          let cnt=0,val=[];
          for(const [k,v] of arr){ //(str, 등장 횟수)
            if(k.length!==course[i])continue; //길이가 다르면 pass
              if(v>cnt && v>1){ //2번이상! 등장해야된다. 최대값 갱신해준다.
                  cnt=v;
                  val=[k];
              }else if(v==cnt){//개수가 같다면 배열에 추가해준다.
                  val.push(k);
              }
        }
          answer=[...answer,...val]; //spread연산자로 간단히 갱신해주기
      }
      
        
    
    
    return answer.sort(); //알파벳 순 정렬하여 리턴해준다.
}