코딩테스트 -- n + 1 카드게임 - (프로그래머스 / C++)

 

프로그래머스

 

 

문제요약!

---

1~n까지의 숫자가 적힌 카드를 무작위로 섞은후, 먼저 n/3장을 뽑아 가진채 게임을 시작합니다

 

각라운드에  2장씩 추가로 뽑아,  주어진 코인을 소모하여 손으로 들고 올 수 있을때,

손에 가진 카드중 2장의 카드의 합을 N+1로 만들어 다음 라운드를 진행 할 수 있습니다. 

 

*합을 n+1을 만들지 못하거나, 섞여있는 n장의 카드뭉치를 모두 소모하면 게임을 종료됩니다.  

 

 

---

 

 

 

단순한 카드게임이지만 코드로 구성하려니.. 머리속이 복잡해 지네요..

 

 

 

 

그럼 바로 코드 시작!

 

---

 

우선 진행하며 2가지 방법으로 시도해보았는데,

 

먼저 첫번째 해결방법으로는 모든 경우에 대해 탑색하는 방법을 사용해 보기로 하였습니다.

 

각 라운드 마다 아래처럼 코인을 몇개 사용할 것인지를 각각 탐색해주는 방식으로 진행해 주었으나..

Game(0, NowCoin - UseCoin, round+1, cards);

        Num_cards[cards[NowCount]] = 1;
        Game(1, NowCoin - UseCoin, round + 1, cards);
        Num_cards[cards[NowCount]] = 0;

        Num_cards[cards[NowCount + 1]] = 1;
        Game(1, NowCoin - UseCoin, round + 1, cards);
        Num_cards[cards[NowCount + 1]] = 0;

        Num_cards[cards[NowCount]] = 1;
        Num_cards[cards[NowCount + 1]] = 1;
        Game(2, NowCoin - UseCoin, round + 1, cards);
        Num_cards[cards[NowCount]] = 0;
        Num_cards[cards[NowCount + 1]] = 0;

 

시간초과되버리네요...

 

카드의 수가 1000장 밖에 되지 않지만 저런식으로 접근하는건 무리가 있어 보였습니다. 

 

 

 

 

 

그다음으로는 손에 든 카드와 뽑을 수 있는카드, 2그룹으로 나누어 생각해주는 방법으로 코드를 구성해보았습니다.

 

 

아래처럼 손에 들고있는 카드와 라운드별 뽑을수 있는 카드들을 배열로 저장해주었습니다.

(배열로 저장한 이유는 나중에 합을 확인할때 MyCardsList[i]+ MyCardsList[n+1-i]의 합으로 확인해주기 위해! )

int n = 0;

int MyCardsList[1001] = { 0, };  //  뽑은 카드들
int CardsList[1001] = { 0, };    //  뽑을 카드들

 

***여기서 CardsList에 저장된 값들은 매 라운드마다 뽑는 2개의 카드뿐만 아니라

현재 라운드까지 뽑을수 있었던 카드들을 뜻합니다!

 

문제에 있는 예시로 보면

 

아래처럼 있을때 

4	[3, 6, 7, 2, 1, 10, 5, 9, 8, 12, 11, 4]

 

 

CardsList의 값들은 매 라운드 초기화 되지 않고 누적되게끔 구성!

 

 

이렇게 누적되게끔 구성해야 모든 부분을 탐색하지 않고,

코인을 어느 숫자를 구매하는데에 사용할지를 구해 줄 수 있습니다.

 

[첫번째 라운드에서 구매하지 않은 숫자가 뒷 라운드에서 필요할 수 도 있기때문!]

 

 

 

 

그럼 이어서

 

solution함수를 선언해주었는데 아래처럼 문제에서 주어진 설명 순서대로 짜주었습니다.

1. n/3만큼 미리뽑고

2. 라운드 마다 진행하며 n+1의 합을 구성할 수 있는지 확인

int solution(int coin, vector<int> cards) {
    int answer = 0;

    n = cards.size();

    int NowCount = n / 3;// 뽑은 카드의 갯수
    int temp = 0;

    for (int i = 0; i < NowCount; i++) { // 내가 가지고 있는 카드 체크
        MyCardsList[cards[i]] = 1;
    }


    for (int i = NowCount; i < n; i += 2) { // 라운드 진행
        answer += 1;
        // 뽑을 카드 저장 (라운드별)
        CardsList[cards[i]] = 1;
        CardsList[cards[i + 1]] = 1;


        if (Cal_MyCards()) { // 현재 손에 있는 카드로 만들기 가능

            continue;
        }


        // 손에 들고 있는 카드들과 합이 n+1이 될수 있는 카드리스트 찾기
        temp = Cal_N();

        if (temp && coin >= temp) {
            coin -= temp;
        }
        else {
            return answer;
        }
    }

    return answer + 1;
}

 

 

 

여기서 현재 손에 있는 카드만을 가지고 n+1을 구해줄 Cal_MyCards를 구성해주었고,

int Cal_MyCards() {

    for (int i = 1; i <= n; i++) { // 절반 
        if (MyCardsList[i] == 1 && MyCardsList[n + 1 - i] == 1) { // 13만들기 가능
            MyCardsList[i] = 0;
            MyCardsList[n + 1 - i] = 0;

            return i;
        }
    }

    return 0;
}

 

 

 

 

뽑을 수 있는 카드들과 손에 있는 카드들을 이용해서 합을 구해줄 Cal_N 함수를 구성

int Cal_N() { // 2장중에 뽑을 카드 반환

    for (int i = 1; i <= n; i++) {
        if (MyCardsList[i] == 1 && CardsList[n + 1 - i] == 1) { // 1장을 뽑아 해결
            MyCardsList[i] = 0;
            CardsList[n + 1 - i] = 0;
            return 1;
        }
    }

    for (int i = 1; i <= n; i++) {
        if (CardsList[i] == 1 && CardsList[n + 1 - i]) { // 2장을 뽑을 경우
            CardsList[i] = 0;
            CardsList[n + 1 - i] = 0;
            return 2;
        }
    }

    return 0; // 못만듬
}

 

Cal_N 함수의 경우 먼저 손에 있는 카드 1장 + 뽑을 수 있는카드 1장 의 경우부터 생각해주고,

2장다 뽑을 경우를 생각해주게끔 구성했습니다. 

 

 

 

각 함수별로 생각해보면

 

Cal_MyCards => 코인을 0개사용

Cal_N  = > 코인을 1,2개사용 

으로 볼 수 있습니다!

 

 

++ 그리고 solution 함수에 마지막 리턴값으로 라운드값에 +1 해주는 부분을 주의해주세요

(카드뭉치를 모두 사용했는지 확인하는 부분도 한 라운드로 취급)

 

....

}

    return answer + 1;
}

 

 

여기까지....

문제 그대로 구성하면 순조롭게 풀리는 문제였지만, 생각하기에 따라 시간이 꽤 걸리는 문제였던것 같습니다. 

 

조건을 잘 확인하고 무엇보다 문제를 일으킬수 있는 예외사항에 대해서 잘 생각해봐야 할 것 같네요... 끝!

 

 

 

ALL

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>


using namespace std;

int n = 0;

int MyCardsList[1001] = { 0, };  //  뽑은 카드들
int CardsList[1001] = { 0, };    //  뽑을 카드들 

vector<int>TempList; // 사용가능한 카드들 임시저장


// 뽑을 카드와 짝이 되는 카드가 손에 있다면 코인을 소모해주기 

int Cal_N() { // 2장중에 뽑을 카드 반환

    for (int i = 1; i <= n; i++) {
        if (MyCardsList[i] == 1 && CardsList[n + 1 - i] == 1) { // 1장을 뽑아 해결
            MyCardsList[i] = 0;
            CardsList[n + 1 - i] = 0;
            return 1;
        }
    }

    for (int i = 1; i <= n; i++) {
        if (CardsList[i] == 1 && CardsList[n + 1 - i]) { // 2장을 뽑을 경우
            CardsList[i] = 0;
            CardsList[n + 1 - i] = 0;
            return 2;
        }
    }
    

    return 0; // 못만듬
}

int Cal_MyCards() {

    for (int i = 1; i <= n; i++) { // 절반 
        if (MyCardsList[i] == 1 && MyCardsList[n + 1 - i] == 1) { // 13만들기 가능
            MyCardsList[i] = 0;
            MyCardsList[n + 1 - i] = 0;

            return i;
        }
    }
    return 0;
}


int solution(int coin, vector<int> cards) {
    int answer = 0;

    n = cards.size();

    int NowCount = n / 3;// 뽑은 카드의 갯수
    int temp = 0;




    for (int i = 0; i < NowCount; i++) { // 내가 가지고 있는 카드 체크
        MyCardsList[cards[i]] = 1;
    }


    for (int i = NowCount; i < n; i += 2) { // 라운드 진행
        answer += 1;
        // 뽑을 카드 저장 (라운드별)
        CardsList[cards[i]] = 1;
        CardsList[cards[i + 1]] = 1;


        if (Cal_MyCards()) { // 현재 손에 있는 카드로 만들기 가능

            continue;
        }


        // 손에 들고 있는 카드들과 합이 n+1이 될수 있는 카드리스트 찾기
        temp = Cal_N();

        if (temp && coin >= temp) {
            coin -= temp;
        }
        else {
            return answer;
        }
    }

    return answer+1;
}