프로그래머스: n+1 카드게임 - javascript(구현, 조합)

문제 출처 

https://school.programmers.co.kr/learn/courses/30/lessons/258707

프로그래머스

 

문제 풀이 힌트

음, 이 문제는 카드를 선택하고, 넣고 , 빼고 이런식으로 접근하면 절대 못 풀 것 같다. 

일단 평범한 나는 그렇다 !!

 

그 이유는 문제 예시를 봐보자. 

1라운드에서 뽑을 수 있는 카드 1,10 이 있다고 치자. 이거를 keep 해놨다가 갑자기 3라운드에서 쓸 수 있는 게임이다. 

=> 이걸 어떤식으로 표현할지,,,? 난 모르겠다 ;; 

 

그리고, 두번째 이유로는 문제를 계속 풀다보니 느낀건데, 무언가를 삽입하고 삭제하는건 시간 복잡도에 정말 좋지 않고, 코드도 작성하다가 내가 헷갈려서 못한다. 

 

그럼 어떻게 하나요?? 

 

이럴 때는 범위로 생각하자. 

 

1라운드에서는 idx 0 ~ idx5까지 카드 조합을 살펴보고, 합이 target 즉 13과 일치하면 그 카드 조합을 내는 것이다 !!! 

2라운드에서는 idx 0 ~ idx7까지 ,

3라운드에서는 idx 0 ~ idx9까지 ,

4라운드에서는 idx 0 ~ idx11까지, 

 

이렇게 생각하면 keep 이라는 설정이 구현 가능하다. (1라운드에서 뽑을 수 있는 카드를, 3라운드에서도 뽑을 수 있게 되니까)

 

두번째로 생각해줘야 하는건,,, 

지금 target이 된, 합이 13인 카드 조합들 중에 도대체 무엇을 낼 것이냐?

여기선 문제가 갑자기 그리디가 된다. 

뭘 것 같으신가요? 

=> coin 아끼는게 최고다 ~~ 내 원래 카드 ([3,6,7,2]) 요것을 최대한 쓰는 것이 좋다. 

 

즉, [6,7]과 [3,10] 이라는 선택지가 있을 때 일단 [6,7] 내자 이거다 ~~ 

 

이 두개만 조심해주면 나머진 문제 구현이다.  

 

코드에 주석처리로 작성했다..! 

 

정답 풀이 코드 

function solution(coin, cards) {
    let round = 1
    let n = cards.length/3
    let target = cards.length + 1
    let remove_cards = []; //제출한 카드는 여기다 push한다. 
    let real_card = cards.slice(0,n) //원래 가지고 있는 카드들
    
    for(let i=n+2; i<=cards.length+1; i+=2){
        let cur_cards = cards.slice(0, i).filter(el => !remove_cards.includes(el)) 현재 범위내 카드 중에서 제출한 카드는 계속 제외시킨다. 
        let combinations = getCombination(cur_cards, 2) //카드 두개씩 조합들
        let possible_submit = sumTarget(combinations, target) //해당 조합들 중 target 13 합이 되는 카드들만 출력
        if(possible_submit.length === 0) return round; //낼 수 있는게 없으면 현재 라운드에서 끝
        
        //제출 가능한 카드들 중, coin 적게 쓰는 카드 조합으로 제출할 것임!
        let min = Number.MAX_SAFE_INTEGER; 
        let select_submit = []
        for(let candi of possible_submit){
            let coin_cnt = checkCoin(real_card, i, candi)//coin 몇개 쓰는지 확인
            if(min > coin_cnt){ //최솟값보다 더 적은 coin 을 쓴다면, 
                 min = coin_cnt; 
                select_submit = candi //이 조합 카드로 대체 
            }
        }             
        if(min > coin) return round; //만약 coin이 부족하면 round 여기서 끝
        
        round++ //다음 라운드 가자 
        coin -= min; //내가 쓴 coin 개수만큼 빼준다. 
        remove_cards.push(...select_submit) //내가 제출한 카드들 remove_cards에 넣어놓자. 
    }
  return round; 
    
    //제출해야 하는 카드가 동전 써야 하는 카드 몇개인지 확인하는 코드 
    //arr이 본래 가지고 있는 카드다. 내가 제출할 수도 잇는 카드 후보랑 비교해서 coin 몇개 쓰는지 출력
    function checkCoin(arr, n, card){
        let cnt = 0; 
        for(let i=0; i<card.length; i++){
            if(!arr.includes(card[i])) cnt++; 
        }
        return cnt; 
    }
    
    //조합들 중 합이 target이 되는거 배열에 모두 출력, 없으면 false
    //간단한 함수다. [a,b] a+b 합이 target이 되면 results에 push 
    function sumTarget(combinations, target){
        let results = []; 
        combinations.forEach((combi) => {
           let sum = combi.reduce((a,b) =>a+b)
           if(sum === target) results.push(combi)
        })
        return results
    }
    
    //현재 범위 내 카드들 중 두개씩 조합 
    function getCombination(arr, selectNum){
    let results = [];
    if(selectNum === 1) return arr.map(v => [v]); 
    arr.forEach((fixed, idx, origin) => {
        const rest = origin.slice(idx+1)
        const combinations = getCombination(rest, selectNum-1)
        const attached = combinations.map((combi) => [fixed, ...combi])
        results.push(...attached)
    })
    return results; 
}
}

Only 정답 코드 

function solution(coin, cards) {
    let round = 1
    let n = cards.length/3
    let target = cards.length + 1
    let remove_cards = []; 
    let real_card = cards.slice(0,n)
    for(let i=n+2; i<=cards.length+1; i+=2){
        let cur_cards = cards.slice(0, i).filter(el => !remove_cards.includes(el))
        let combinations = getCombination(cur_cards, 2)
        let possible_submit = sumTarget(combinations, target)
        if(possible_submit.length === 0) return round; 
        let min = Number.MAX_SAFE_INTEGER; 
        let select_submit = []
        for(let candi of possible_submit){
            let coin_cnt = checkCoin(real_card, i, candi)
            if(min > coin_cnt){
                 min = coin_cnt; 
                select_submit = candi
            }
        }             
        if(min > coin) return round; 
        round++
        coin -= min; 
        remove_cards.push(...select_submit)
    }
  return round; 
    
    function checkCoin(arr, n, card){
        let cnt = 0; 
        for(let i=0; i<card.length; i++){
            if(!arr.includes(card[i])) cnt++; 
        }
        return cnt; 
    }
    
    function sumTarget(combinations, target){
        let results = []; 
        combinations.forEach((combi) => {
           let sum = combi.reduce((a,b) =>a+b)
           if(sum === target) results.push(combi)
        })
        return results
    }
    
    function getCombination(arr, selectNum){
    let results = [];
    if(selectNum === 1) return arr.map(v => [v]); 
    arr.forEach((fixed, idx, origin) => {
        const rest = origin.slice(idx+1)
        const combinations = getCombination(rest, selectNum-1)
        const attached = combinations.map((combi) => [fixed, ...combi])
        results.push(...attached)
    })
    return results; 
}
}

 

배우고 가는 것.  

문제 설계

- 빠르게 푸는 것이 오히려 문제 푸는데 효과적이다. 

- 문제를 세세하게 정리하지 마라 

- 어떤 식으로 문제를 풀지 그림으로 그려서 설계를 한다. 

- 중간중간 확인하면서 풀지 말고, 전체 흐름 계속 잡으면서 코드 다 작성한다. 그 후에 검증 한다.