« 2024/09 »
일	월	화	수	목	금	토
1	2	3	4	5	6	7
8	9	10	11	12	13	14
15	16	17	18	19	20	21
22	23	24	25	26	27	28
29	30

(2024 KAKAO WINTER INTERNSHIP) n + 1 카드게임

카테고리

코딩테스트 문제 풀이

작성일

2024. 3. 11. 17:00

작성자

WDmil

728x90

문제 설명

당신은 1~n 사이의 수가 적힌 카드가 하나씩 있는 카드 뭉치와 동전 coin개를 이용한 게임을 하려고 합니다. 카드 뭉치에서 카드를 뽑는 순서가 정해져 있으며, 게임은 다음과 같이 진행합니다.

처음에 카드 뭉치에서 카드 n/3장을 뽑아 모두 가집니다. (n은 6의 배수입니다.) 당신은 카드와 교환 가능한 동전 coin개를 가지고 있습니다.

게임은 1라운드부터 시작되며, 각 라운드가 시작할 때 카드를 두 장 뽑습니다. 카드 뭉치에 남은 카드가 없다면 게임을 종료합니다. 뽑은 카드는 카드 한 장당 동전 하나를 소모해 가지거나, 동전을 소모하지 않고 버릴 수 있습니다.

카드에 적힌 수의 합이 n+1이 되도록 카드 두 장을 내고 다음 라운드로 진행할 수 있습니다. 만약 카드 두 장을 낼 수 없다면 게임을 종료합니다.

예를 들어 n = 12, coin = 4이고 [3, 6, 7, 2, 1, 10, 5, 9, 8, 12, 11, 4] 순서대로 카드를 뽑도록 카드 뭉치가 섞여 있습니다.

처음에 3, 6, 7, 2 카드 4장(= n/3)과 동전 4개(= coin)를 가지고 시작합니다. 다음 라운드로 진행하기 위해 내야 할 카드 두 장에 적힌 수의 합은 13(= n+1)입니다. 다음과 같은 방법으로 최대 5라운드까지 도달할 수 있습니다.

1라운드에서 뽑은 카드 1, 10을 동전 두 개를 소모해서 모두 가집니다. 카드 3, 10을 내고 다음 라운드로 진행합니다. 이때 손에 남은 카드는 1, 2, 6, 7이고 동전이 2개 남습니다.
2라운드에서 뽑은 카드 5, 9를 동전을 소모하지 않고 모두 버립니다. 카드 6, 7을 내고 다음 라운드로 진행합니다. 이때 손에 남은 카드는 1, 2고 동전이 2개 남습니다.
3라운드에서 뽑은 카드 8, 12 중 동전 한 개를 소모해서 카드 12를 가집니다. 카드 1, 12을 내고 다음 라운드로 진행합니다. 이때 손에 남은 카드는 2이고 동전이 1개 남습니다.
4라운드에서 뽑은 카드 11, 4 중 동전 한 개를 소모해서 카드 11을 가집니다. 카드 2, 11을 내고 다음 라운드로 진행합니다. 이때 손에 남은 카드와 동전은 없습니다.
5라운드에서 카드 뭉치에 남은 카드가 없으므로 게임을 종료합니다.

처음에 가진 동전수를 나타내는 정수 coin과 카드를 뽑는 순서대로 카드에 적힌 수를 담은 1차원 정수 배열 cards가 매개변수로 주어질 때, 게임에서 도달 가능한 최대 라운드의 수를 return 하도록 solution 함수를 완성해 주세요.

제한사항

0 ≤ coin ≤ n
6 ≤ cards의 길이 = n < 1,000
cards[i]는 i+1번째로 뽑는 카드에 적힌 수를 나타냅니다.
1 ≤ cards[i] ≤ n
cards의 원소는 중복되지 않습니다.
n은 6의 배수입니다.

입출력 예

coin	cards	result
4	[3, 6, 7, 2, 1, 10, 5, 9, 8, 12, 11, 4]	5
3	[1, 2, 3, 4, 5, 8, 6, 7, 9, 10, 11, 12]	2
2	[5, 8, 1, 2, 9, 4, 12, 11, 3, 10, 6, 7]	4
10	[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18]	1

문제 해설

문제가 IQ테스트마냥, 조건해석을 요구한다.

문제 유형상 조건에 따른 데이터 정리를 해야하는데, 데이터는 다음과 같다.

각 라운드 기준으로 데이터를 정렬해야 하는데, 라운드당 데이터가 정렬되는 기준은,

1 ~ n개 까지의 객체중에서 결과값이 n+1이 되는 경우의 수만 결과값으로 나타나게 됨으로, 1 ~ n까지의 데이터에서 n+1이 되는 경우의 수는, 1 + n , 2 + n-1... 이런식으로 정의된다.

즉, 각 데이터를 정리하면, n / 2개의 데이터로 정리할 수 있는데, n은 항상 6의 배수임으로, 짝수가 보장된다는걸 생각하자.

그리고, 데이터가 들어오게 되는 순서가 다르게 됨으로, 데이터 순서를 따져야 한다.

그리고, 데이터를 받아왔을 때, 필요한 코인의 개수를 감안해야 한다.

순서대로 정리해보면 다음과 같다.

1. 데이터의 들어오는 순서대로 정리하자.

데이터는 n의 3으로 나눈 개수만큼 가지고 시작하고, 각 라운드당 2개씩 받아와 사용하게 된다. 예시 1로 정리하면 다음과 같다.

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

2. 데이터의 들어가는 코인 개수를 정리해보자.

데이터의 코인 개수는, 시작시 0개 나머지는 전부 한개이다. 다음과 같이 정리할 수 있다.

3	6	7	2	1	10	5	9	8	12	11	4
1	1	1	1	1	1	2	2	3	3	4	4
0	0	0	0	1	1	1	1	1	1	1	1

3. 이제 데이터를 1에서부터 끝까지 순서대로 정리해보자.

1	2	3	4	5	6	7	8	9	10	11	12
1	1	1	4	2	1	2	3	2	1	4	3
1	0	0	1	1	0	0	1	1	1	1	1

4. 데이터는 짝수 / 홀수 둘중 한개의 데이터만 사용한다. 결과는 늘 n + 1이 되어야 하기 때문,

1	3	5	7	9	11
1	1	2	2	2	4
1	0	1	0	1	1

위 데이터를 묶을 때는, 1 + 12 = 13 임으로,

1 + 12을 사용하기 위해서는 데이터가 존재해야 함으로, 두개중 라운드가 가장 큰 라운드를 사용해야 한다.

두개를 다 사용하기 위해서는 필요한 코인을 전부 더해서 두개일 경우 2 한개일 경우 1 로 정리해서 사용해야 한다.

위 사실을 바탕으로 다시 정리하면 다음과 같다.

1	3	5	7	9	11
3	1	3	2	4	4
2	1	2	0	2	1

5. 이제 나온 데이터를 라운드 순으로 정리하자.

3	7	1	5	9	11
1	2	3	3	4	4
1	0	2	2	2	1

6. 이제, 라운드를 기준으로 정리된 데이터를 참고하여 라운드 마다 얻을 수 있는 경우를 정리하자.

모든 데이터는 얻을 수 있는 라운드 일 경우, 데이터를 습득하고, 가능한 경우 coin을 소모하여 데이터를 도출시킨다.

이때, coin이 0이 되거나, 마지막 경우의 수에 도달했을 경우, 종료한다.

6. 이걸 라운드순으로, 들어가는 코인을 중첩하여 정리하면 다음과 같다.

라운드	0코인	1코인	2코인
1라운드	0	1	0
2라운드	1	0	0
3라운드	0	0	2
4라운드	0	1	1
5라운드	0	0	0

이제 이걸 라운드 순으로 정리해서 for문을 돌리면된다.

처음 기준, 데이터는 {0, 0, 0}개의 데이터가 존재하고, 코인은 4개가 존재한다.

1라운드 : input {0, 1, 0}, coin 4 | output [ {0, 0, 0} coin 3

{0, 1, 0}이다. 데이터를 도출해야 함으로, coin을 1 소모하여 데이터를 도출한다. 가능한 최소의 코인만 소모해야 한다.

2라운드 : input {1, 0, 0}, coin 3 | output [ {0, 0, 0} coin 3

전값과 합치면 {1, 0, 0}이다. 데이터를 도출해야 함으로, coin을 0 소모하여 데이터를 도출한다.

3라운드 : input {0, 0, 2}, coin 3 | output [ {0, 0, 1} coin 1

전값과 합치면 {0, 0, 2}이다. 데이터를 도출해야 함으로, coin을 2 소모하여 데이터를 도출한다.

4라운드 : input {0, 1, 1}, coin 3 | output [ {0, 0, 2} coin 0

전값과 합치면 {0, 1, 2}이다. 데이터를 도출해야 함으로, coin을 1 소모하여 데이터를 도출한다.

5라운드 : 코인과 아웃풋 전부 0임으로 result = 5

첫 번째 시도

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

using namespace std;

bool sorting(const vector<int>& a, const vector<int>& b)
{
    return a[1] < b[1];
}

int solution(int coin, vector<int> cards) {
    int n = *max_element(cards.begin(), cards.end());
    int c = n / 3;
    int round = 1;

    vector<vector<int>> SVector(n, vector<int>(0));
    for (int i = 0; i < cards.size(); i += 2) {
        if (i < c) {
            SVector[cards[i] - 1].push_back(cards[i]);
            SVector[cards[i + 1] - 1].push_back(cards[i + 1]);
            SVector[cards[i] - 1].push_back(round);
            SVector[cards[i + 1] - 1].push_back(round);
            SVector[cards[i] - 1].push_back(0);
            SVector[cards[i + 1] - 1].push_back(0);
        }
        else {
            SVector[cards[i] - 1].push_back(cards[i]);
            SVector[cards[i + 1] - 1].push_back(cards[i + 1]);
            SVector[cards[i] - 1].push_back(round);
            SVector[cards[i + 1] - 1].push_back(round);
            SVector[cards[i] - 1].push_back(1);
            SVector[cards[i + 1] - 1].push_back(1);
            ++round;
        }

    }
    vector<vector<int>> OddN;
    int size = SVector.size();
    for (int i = 0; i < size; i +=2 )
    {
        vector<int> def(3);
        def[0] = i+1;
        def[1] = max(SVector[i][1], SVector[size - (i + 1)][1]);
        def[2] = SVector[i][2] + SVector[size - i - 1][2];
        OddN.emplace_back(def);
    }

    vector<int> temp(3);
    vector<vector<int>> Cardlist(round-1, vector<int>(3));
    for (auto& def : OddN) ++Cardlist[def[1]-1][def[2]];
    int answer = 1;
    for (auto& def : Cardlist)
    {
        temp[0] += def[0];
        temp[1] += def[1];
        temp[2] += def[2];
        bool chack = false;
        for (int i = 0; i < 3; i++)
            if (temp[i] > 0 && coin - i >= 0)
            {
                --temp[i];
                coin -= i;
                chack = true;
                break;
            }
        if(!chack) return answer;
        answer++;
    }
    
    return answer;
}

성공

데이터의 종류를 어떤식으로 정리하느냐에 따라 달라지는 결과이다.

함수, 알고리즘을 사용하는 경우가 아니라 IQ테스트를 요구하는 문제,