[코딩문제]놀이공원 인형 맞추기

문제 출처 : 코딩도장(http://codingdojang.com/scode/531)

문제

놀이공원에 가면 인형 맞추기 게임이 있다.

한 놀이공원에는 인형에 숫자를 써놓고 인형 맞추기를 한다.

그런데 맞춘 인형의 숫자의 합이 특정한 값이 되는 경우에만 맞춘 인형을 가져 갈 수 있다.

가령 10개의 인형에 쓰여진 숫자가 각각 25 27 3 12 6 15 9 30 21 19이고 

숫자의 합이 50이 되는 경우만 인형을 가져갈수 있다면 

6 19 25가 쓰여진 인형을 맞춰야 인형을 가져 갈 수 있다.

이때 인형의 갯수와 각각의 숫자와 필요한 합을 입력받으면 

맞춰야 하는 인형의 숫자를 출력하는 프로그램을 작성해 보자.

입력 - 첫줄에는 인형의 갯수와 필요한 합, 둘째 줄에는 인형 각각에 쓰여진 숫자

예)

10 50

25 27 3 12 6 15 9 30 21 19

출력 - 필요한 합이 되는 인형 각각의 숫자를 오름차순으로 출력

예)

6 19 25

코딩 해결 : 내 손과 머리 (Visual Studio 2013)

#include <iostream>

#include <sstream>

#include <vector>

#include <list>

using namespace std;

//표준 숫자 입력 함수

vector<int> getInput(size_t sizeLimit)

{

vector<int> vToken;

vToken.reserve(sizeLimit);

string line;

getline(cin, line);

istringstream iss(line);

string token;

while (getline(iss, token, ' ')) 

{

try 

{

vToken.push_back(stoi(token));

}

catch (exception& e) 

{

continue;

}

if (vToken.size() >= sizeLimit) {

break;

}

}

return vToken;

}

//정렬함수(선택정렬) - 내림차순

void SortR(vector<int>& v)

{

int dollsCount = v.size();

int dollsCountM1 = dollsCount - 1;

for (int i = 0; i < dollsCountM1; ++i)

{

int lastIndex = i;

bool bChange = false;

for (int j = i + 1; j < dollsCount; ++j)

{

if (v[lastIndex] < v[j]) //내림차순

{

bChange = true;

lastIndex = j;

}

}

if (bChange)

{

//이동함수를 이용한 순수 스왑 - c++11

int temp = move(v[i]);

v[i] = move(v[lastIndex]);

v[lastIndex] = move(temp);

}

}

}

//출력 함수

void Print(vector<int>& v)

{

for (auto iter = v.begin(); iter != v.end(); ++iter)

{

cout << *iter << ' ';

}

}

//결과 출력 함수

void PrintResult(list<int>& v)

{

for (auto iter = v.begin(); iter != v.end(); ++iter)

{

*iter == -1 ? cout << endl : cout << *iter << ' '; //삼항연산

}

}

//탐색 함수

void SeachNum(vector<int>& v, list<int>& result, list<int>& tempList, int start, int end, int sNum)

{

if (v[start] == sNum) //첫 숫자와 결과 수가 맞다면

{

result.push_back(-1); //구분자 입력

result.push_back(v[start]); //현재 숫자 입력

if (!tempList.empty()) //임시 리스트가 비어 있지 않다면

{

result.insert(result.end(), tempList.begin(), tempList.end()); //지금까지의 임시 리스트(부모) 입력

}

}

else if (v[start] < sNum)    //결과 값이 더 클 경우

{

int searchNewNum = sNum - v[start];    //구해야 할 값 갱신

for (int i = start + 1; i < end; ++i) //정렬된 현재의 다음 노트 부터

{

tempList.push_front(v[start]); //부모를 나타내기 위해 임시 리스트 앞에 입력

SeachNum(v, result, tempList, i, end, searchNewNum); //재귀

tempList.pop_front(); //재귀가 끝나면 리스트 앞을 다시 비움

}

}

//else if (v[start] > sNum) //무시

}

int main(void)

{

//자연수 2개 받기 - 인형 갯수, 필요 합

vector<int> stdNum = getInput(2);

int dollsCount = stdNum[0]; //인형 갯수

int sumNums = stdNum[1]; //필요 합

//인형 숫자들 입력

vector<int> vNumbers = getInput(dollsCount);

//정렬 - 내림차순

SortR(vNumbers);

//출력

Print(vNumbers);    //정렬된 벡터 출력

//결과 받을 리스트

list<int> vResults;

//임시 리스트

list<int> vTemps;

//탐색

for (int i = 0; i < dollsCount; ++i)

{

SeachNum(vNumbers, vResults, vTemps, i, dollsCount, sumNums);

}

//결과 출력

cout << endl;

PrintResult(vResults);

//getchar();

return 0;

}

처음에 내림 차순으로 큰 숫자부터 정렬 한것은

깊이우선 탐색을 생각하다보니

더 많은 연산을 제한하기 위해서

결과 합에서 작은 수부터 빼나아가 찾는 것보다

큰 수를 빼나아가 찾는 것이 연산이 적을 것이라 예상 했기 때문 입니다.

리스트와 벡터의 복합 사용 이유는

고정된 메모리 상의 데이터를 처리하고자 할 경우 벡터

자주 삽입, 삭제가 이루어 지는 것은 리스트로 처리하여 

연산이나 메모리에 부담을 덜어주고자 하였습니다.