[백준][C++]16566 - 카드 게임(실패)

문제

• 16566번 : 카드 게임
• Rank : Emerald V
• 링크

16566번: 카드 게임

 

풀이 전략

• STL::Vector을 사용하여 한번에 입력받은 후 정렬 실행
  
  • 입력 이전에 reserve 공간 확보(대량의 move 실행 방지)
• 카드 입력을 비교하여 상대방의 카드가 MAX 이상, MIN 이하일 경우, 최저 카드를 제출
• 중간값일 경우 이진 검색을 실행하여 해당 카드를 이길 수 있는 카드를 찾아 제출
• 제출 후, 뽑은 카드는 Vector에서 삭제

결과

• 공개Test case, 자체 Test Case는 성공하나, 제출 진행시 시간부족으로 실패 처리
• 백준 테스트 환경에서 대형 케이스(카드 4백만, 뽑을 카드 1만)를 시도할 경우, 시간부족으로 실패하는 것으로 보임.
• Vector 대신 자체 이진 그래프를 작성하여 시도해볼 것

 

소스 코드

//Backjoon Problem No.16566
//Mist16, 2022-01-21

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

using namespace std;


class cardDeck
{
private:
	vector<int> cardSet;

public:

	void setSize(int num)
	{
		cardSet.reserve(num);
	}
	void insertCard(int num)
	{
		cardSet.push_back(num);
	}

	void sortCards()
	{
		sort(cardSet.begin(), cardSet.end());
	}
    
	void deleteCard(vector<int>::iterator iter)
	{
		cardSet.erase(iter);
	}

	vector<int>::iterator getMinCard()
	{
		auto iter = cardSet.begin();
		return iter;
	}
	vector<int>::iterator getMaxCard()
	{
		auto iter = cardSet.end();
		iter--;
		return iter;
	}

	int popCard(int target)
	{
		vector<int>::iterator popOutCard;
		int outCardNum;
		if (target >= *getMaxCard() || target <= *getMinCard()) //losing hand
		{
			popOutCard = getMinCard();
			outCardNum = *popOutCard;
			deleteCard(popOutCard);
			return outCardNum;
		}
		else
		{
			popOutCard = findCard(target);
			outCardNum = *popOutCard;
			deleteCard(popOutCard);
			return outCardNum;
		}
	}

	vector<int>::iterator findCard(int target)
	{
		auto start = cardSet.begin();
		auto end = cardSet.end() - 1;
		int size = cardSet.size();

		while (1)
		{
			auto middle = start + (size / 2);
			if (size == 1)
			{
				return start;
			}
			size = size - (size / 2);

			if (*middle == target)
			{
				return middle + 1;
			}
			else if (*middle < target)
			{
				start = middle;
				continue;
			}
			else
			{
				end = middle;
				continue;
			}
		}
	}

};

int N, M, K;
cardDeck myDeck;

int main()
{
	int cardNum = 0;

	//입출력 속도 관리용
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N >> M >> K;

	//reserve 함수를 사용하여, 미리 vector의 공간을 확보해둔다
	myDeck.setSize(M);

	for (int i = 0; i < M; i++)
	{
		cin >> cardNum;
		myDeck.insertCard(cardNum + 1);
	}
	myDeck.sortCards();

	for (int i = 0; i < K; i++)
	{
		cin >> cardNum;
		cout << myDeck.popCard(cardNum) << "\n";
	}
}