프로그래머스 - 단체사진 찍기 (C++)

https://school.programmers.co.kr/learn/courses/30/lessons/1835

프로그래머스

 이번 문제는 각 프렌즈가 줄을 서기를 원하는 조건들이 주어졌을 때, 적절한 줄의 개수를 구하는 문제이다. 이 문제를 풀기 위해서는 순열이라는 개념을 알아야 한다. 만약 1번 사람, 2번 사람, 3번 사람을 줄을 세웠을 때, 1번-2번-3번 순으로 줄을 서는 것과 2번-3번-1번 순으로 줄을 서는 것을 다르게 취급하는 경우를 순열이라 한다. 즉, 이 문제에서는 어피치부터 튜브까지 줄을 세울 수 있는 모든 경우를 검사해야 하는데, 이를 순열을 이용해서 구할 수 있다. 문제를 해결하기 위해 구상한 절차는 다음과 같다.

1. 모든 값들을 초기화한다.
2. 순열 개념을 이용해 줄을 세운 후, 줄이 세워졌을 때 검사한다.
   1. 모든 사람들을 한 번씩 검사하면서, 줄을 서지 않았다면 줄을 세운다.
   2. 만약 모든 사람들이 줄을 섰다면, 이 줄이 가능한 줄인지 확인한다.
      1. 현재 각 사람들의 줄 위치를 저장한다.
      2. 모든 조건들을 하나씩 검사하면서, 가능한 줄인지 확인한다.
      3. 만약 불가능한 줄이라면, return으로 빠져나간다.
      4. 만약 가능한 줄이라면 답을 +1 한다.

 

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

using namespace std;

#define MAX 8

// 문제에서 주어지는 조건들의 타입형
typedef struct
{
	int person1;
	int person2;
	char type;
	int distance;
} Condition;

int answer = 0;		// 답을 젖아할 변수
bool checked[MAX];	// i번 사람이 줄을 섰는지를 저장할 변수
int personPos[MAX];	// i번 사람의 현재 줄 위치
vector<int> line;	// 사람들이 선 줄
vector<Condition> conditions;	// 주어진 조건들을 저장할 배열
map<char, int> personIdx;		// A 등의 사람 이름을 숫자로 바꾸기 위함

void Check()
{	
	// 2-2, 만약 모든 사람들이 줄을 섰다면, 이 줄으 기능한 줄인지 확인한다.
	if (line.size() >= MAX)	
	{	
		bool success = true;	// 현재 줄이 가능한 줄이라면 true

		// 2-2-1. 현재 각 사람들의 줄 위치를 저장한다.
		for (int i = 0; i < line.size(); ++i)
		{
			int curPerson = line[i];
			personPos[curPerson] = i;
		}

		// 2-2-2. 모든 조건들을 하나씩 검사하면서 가능한 줄인지 확인한다. 
		for (int i = 0; i < conditions.size(); ++i)
		{
			Condition condition = conditions[i];
			
			int person1Pos = personPos[condition.person1];
			int person2Pos = personPos[condition.person2];

			switch(condition.type)
			{
				case '=':
					if (abs(person1Pos - person2Pos) != condition.distance)
						success = false;
						break;
				case '>':
					if (abs(person1Pos - person2Pos) <= condition.distance)
						success = false;
						break;
				case '<':
					if (abs(person1Pos - person2Pos) >= condition.distance)
						success = false;
						break;
			}

			// 2-2-3. 만약 불가능한 줄이라면 return으로 빠져나간다.
			if (success == false)
				return;
		}
		
		// 2-2-4. 만약 가능한 줄이라면 답을 +1 한다.
		++answer;
		return;
	}
	
	// 2-1. 모든 사람들을 한 번씩 검사하면서, 줄을 서지 않았다면 줄을 세운다.
	for (int i = 0; i < MAX; ++i)
	{
		if (checked[i] == false)
		{
			checked[i] = true;
			line.push_back(i);

			Check();

			line.pop_back();
			checked[i] = false;
		}
	}
}

int solution(int n, vector<string> data) 
{	
	// 1. 전부 초기화한다.
	answer = 0;

	for (int i = 0; i < MAX; ++i)
	{
		checked[i] = false;
		personPos[i] = -1;
	}

	line.clear();
	conditions.clear();

	personIdx['A'] = 0;
	personIdx['C'] = 1;
	personIdx['F'] = 2;
	personIdx['J'] = 3;
	personIdx['M'] = 4;
	personIdx['N'] = 5;
	personIdx['R'] = 6;
	personIdx['T'] = 7;

	for (int i = 0; i < data.size(); ++i)
	{
		string curData = data[i];

		Condition condition;
		condition.person1 = personIdx[curData[0]];
		condition.person2 = personIdx[curData[2]];
		condition.type = curData[3];
		condition.distance = curData[4] - '0' + 1;

		conditions.push_back(condition);
	}

	// 2. 순열 개념을 이용해 줄을 세운 후, 줄이 세워졌을 때 검사한다. 
	Check();

	return answer;
}