[문제해결기법] 카드게임(도둑 잡기)

#include <iostream> #include <fstream> #include <vector> #include <functional> #include <algorithm> #include <string> using namespace std; #define MAKE_INDEX(num1,num2) num2 > person_count ? num1 = 1 : num1 = num2 ofstream fcout; vector<vector<int>> person_card; int person_count; /* 이 문제의 관건은 1) 게임을 코드로 구현하는 것과 2) 처음 입력할때 같은 수가 들어오면 삭제해주고 시작한다는 것이다 아니면 탁구처럼 계속 돈다. -> 무한루프발생 */ int play_game() { int before_index = 1, present_index = 1, delete_index; while (1) { //b의 카드를 a로 뺏어옴 //before_index = a / present_index = b 와 같음 MAKE_INDEX(before_index, present_index); while (person_card[before_index].empty()) MAKE_INDEX(before_index, before_index + 1); MAKE_INDEX(present_index, before_index + 1); while (person_card[present_index].empty()) MAKE_INDEX(present_index, present_index + 1); if (before_index == present_index) break; //두개의 index가 같다 -> empty()인 배열이 하나뿐이다. if (person_card[present_index].size() > before_index) delete_index = before_index - 1; //만약 b에 a번째의 카드가 존재한다면 -> b[a]카드를 들고온다 else delete_index = person_card[present_index].size() - 1; //만약 b에 a번째의 카드가 존재하지 않는다면 -> b[b.size()-1] 가장 마지막 카드를 들고온다. fcout << "card " << person_card[present_index][delete_index] << " from " << present_index << " to " << before_index << endl; vector<int>::iterator iter; //찾아보자! iter = find(person_card[before_index].begin(), person_card[before_index].end(), person_card[present_index][delete_index]); if (iter != person_card[before_index].end()) person_card[before_index].erase(iter); //만약 있다면 a에서 b[a]숫자 삭제 else //없다면 a에 b[a]숫자를 넣고 sorting시킨다 -> 순서대로 맞출꺼니까! { person_card[before_index].insert(person_card[before_index].begin(), person_card[present_index][delete_index]); sort(person_card[before_index].begin(), person_card[before_index].end()); } person_card[present_index].erase(person_card[present_index].begin() + delete_index); //그다음 b에서도 a번째의 카드를 지운다! } return before_index; } int main() { ifstream fcin; ifstream fanswer; fcin.open("C_input.txt"); fcout.open("C_answer.txt"); fanswer.open("C_output.txt"); int for_count, card_count, k; string input, temp; fcin >> for_count; for (int i = 0; i<for_count; i++) { fcin >> card_count >> person_count; person_card = vector<vector<int>>(person_count + 1); getline(fcin, input); //flush를 없애주기 위해 getline을 한번 더 쓴다. temp.clear(); //temp도 찝찝하니까 비워주고 for (int j = 1; j <= person_count; j++) //person수만큼 배열에 넣는다. { input.clear(); getline(fcin, input); k = 0; //getline으로 string을 받아서 넣는다. /* input[k]==' '일때만 배열에 삽입한다면 1) 만약 "2 4 5 6 "이 있다. 그렇다면 아래처럼 돌리지 않아도 괜찮다. 왜냐하면 6뒤에 공백이 있으니까 input[k]==' ' 조건만 써도 맞을 것이다. 2) 하지만 "2 4 5 6"이 있다고 치자. 이 예시는 6이 배열에 들어가지 않을것이다. 왜냐하면 마지막에 공백이 없으니까 삽입하지 않는다. 때문에 아래와 같은 조건이 필요하다. */ while (1) { if (temp.empty() && k >= input.size()) break; //temp도 없고(넣어야 할 수가 없고) && (input도 모두 둘러보았을때) -> 나간다 if ((!temp.empty() && k >= input.size()) || input[k] == ' ') //(input을 모두 둘러보았는데) && temp가 있을때 2)번예시와 같을때=(마지막에 공백이 없을때) //혹은 공백을 받았을때 -> 숫자는 공백으로 구별하기 때문 { if (person_card[j].size() == 0) person_card[j].push_back(atoi(temp.c_str())); //만약 배열에 처음부터 아무것도 없었다면 무조건 넣는다. else if (atoi(temp.c_str()) == person_card[j][person_card[j].size() - 1]) person_card[j].erase(person_card[j].end() - 1); //배열에 있다면 배열의 마지막 수와 지금 들어온 숫자를 비교한다. -> 같다면 삭제 else person_card[j].push_back(atoi(temp.c_str())); //같지 않다면 삽입 temp.clear(); //temp clear } else temp.push_back(input[k]); //아니면 temp에 수를 넣는다. //왜 이 과정을 하느냐!! 100이 들어왔다고 하자 char형은 한개만 읽기 때문에 100이아닌 1 0 0이 저장될 것이다 //따라서 공백으로 숫자를 비교할 것이고 공백이 들어오기 전 들어온 모든 숫자는 하나로 볼것이다. k++; //k는 무조건 돌린다. 배열의 크기를 넘어도 상관없다 -> 예외처리를 모두해줬기 때문에! } } int answer; fanswer >> answer; fcout <<i<<"번째"<<endl; int my_answer = play_game(); if (my_answer == answer) cout << my_answer << endl; else cout << my_answer << " : wrong" << endl; fcout << endl; } system("pause"); }