[프로그래머스] 단체사진 찍기 (2017 카카오코드 본선) (level 3)

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/1835

 

 

 문제를 읽으면 제일 빠르게 떠오르는 풀이는 줄을 모든 경우의 수로 세워본 다음 조건에 맞는지 확인하는 방법일 것이다. 친구의 수가 8명이다 보니 줄 세우는 모든 경우의 수는 8!=40320밖에 안된다. 물론 하나의 경우의 수마다 조건을 확인하는 방법이 복잡하다면 충분히 시간 초과가 날 수 있지만 조건 확인하는 연산은 O(1)이고 조건의 개수는 100개 이하이니 시간 초과는 나지 않을 것을 예상할 수 있다.

 

<전체적인 알고리즘>

1. dfs를 이용하여 모든 경우의 수로 줄을 세워본다.

2. 줄을 세웠으면 isright 함수로 조건에 맞는지 확인을 해본다.

3. 조건에 맞으면 result를 증가시킨다.

 

<전체 코드>

#include<iostream>
#include<vector>
#include<string>

using namespace std;

int n;
vector<string> data1;
bool check[10];
int result=0;
string friends = "ACFJMNRT";

bool isright(string str)    //현재 줄 상태가 조건에 성립하는지 확인
{	
	for (int i = 0; i < data1.size(); i++)
	{
		string condition = data1[i];
		int index1 = 0;
		int index2 = 0;
		for (int j = 0; j < str.size(); j++)
		{
			if (str[j] == condition[0])index1 = j;
			else if (str[j] == condition[2])index2 = j;
		}

		int gap = abs(index1 - index2)-1;  // 본인과 상대방 사이의 친구 수

		int condition_gap = condition[4] - '0';  //조건에서의 gap

		if (condition[3] == '=')  //등호일 때 다르면 false
		{
			if (gap != condition_gap)return false;  
		}
		else if (condition[3] == '<')  //미만일 때 크거나 같으면 false
		{
			if (gap >= condition_gap)return false;
		}
		else                  // 초과일 때 작거나 같으면 false
		{
			if (gap <= condition_gap)return false;
		}
	}
	return true;   //조건 모두 통과하면 true;
}

void dfs(string tmp, int count)  //모든 경우의 수 줄 세우기
{
	if (count == 0)   //줄 다 세웠으면
	{
		bool istrue=isright(tmp);  //현재 줄상태가 조건에 성립하는지
		if (istrue)result++;   //조건 성립하면 경우의 수 증가
		return;
	}
	for (int i = 0; i < 8; i++)
	{
		if (check[i])continue;
		check[i] = true;
		char c = friends[i];
	
		tmp += c;
		dfs(tmp, count - 1);
		tmp.pop_back();
		check[i] = false;
	}
}

// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
int solution(int nn, vector<string> data) {
    
    n=nn;
    data1=data;
    fill(&check[0],&check[9],0);
    result=0;
    
    dfs("",8);
    
    return result;
}

 

궁금하신 점은 댓글에 남겨주시면 답변드리겠습니다.