프로그래머스 - 위장(Level 2)/Wanna Be 컴잘알

문제 출처 - https://programmers.co.kr/learn/courses/30/lessons/42578#

코딩테스트 연습 - 위장 | 프로그래머스

 

- 문제 -

 

스파이들은 매일 다른 옷을 조합하여 입어 자신을 위장합니다.

예를 들어 스파이가 가진 옷이 아래와 같고 오늘 스파이가 동그란 안경, 긴 코트, 파란색 티셔츠를 입었다면 다음날은 청바지를 추가로 입거나 동그란 안경 대신 검정 선글라스를 착용하거나 해야 합니다.

종류	이름
얼굴	동그란 안경, 검정 선글라스
상의	파란색 티셔츠
하의	청바지
겉옷	긴 코트

스파이가 가진 의상들이 담긴 2차원 배열 clothes가 주어질 때 서로 다른 옷의 조합의 수를 return 하도록 solution 함수를 작성해주세요.

 

- 접근 -

1. 모든 경우의 수를 일일이 구해주는 방법을 사용하면 시간초과가 발생할 확률이 높다. dfs를 사용하여 모든 경우의 수를 다 세어보려고 했지만 몇몇 케이스에서 시간초과가 발생하였다. 따라서 수학 문제풀듯 종류를 분리하고 조합의 갯수가 몇개인지만 구하면된다.

2. 예를들면 얼굴 3개, 상의 4개, 하의5개이면  (3+1)*(4+1)*(5*1) -1 로 경우의 수를 구할 수 있다.

(+1은 안입는 경우의수, -1은 모두다 안입는 경우는 없으므로 해당 경우를 빼준다.)

 

cf) 혹시 모든 조합을 구하는 방법이 궁금하다면 참고 코드를 참고하면 되겠다.

 

- 코드 -

 

정답 코드)

#include <string>
#include <string.h>
#include <vector>
#include <set>
#include <iostream>
using namespace std;

int solution(vector<vector<string>> clothes) {
	int answer = 1;
	int kind_cnt = 0; //종류개수
	set <string> clothes_kind;

	for (int k = 0; k < clothes.size(); k++) {
		clothes_kind.insert(clothes[k][1]);
	}
	
	vector <pair<string, int>> v;

	for (auto k : clothes_kind) {
		v.push_back({ k,0 });
	}
	
	for (int k = 0; k < clothes.size(); k++) {
		string clo_kind = clothes[k][1];
		for (int i = 0; i < v.size(); i++) {
			if (clo_kind == v[i].first) {
				v[i].second += 1;
			}
		}
	}

	for (int k = 0; k < v.size(); k++) {
		answer *= (v[k].second + 1);
	}
	answer -= 1;

	return answer;
}

 

참고 코드)

#include <string>
#include <string.h>
#include <vector>
#include <set>
#include <iostream>
using namespace std;
// 5+4+3, 5x4, 4x3, 5x3, 5x4x3
bool check[30];
int answer = 0;
void solve(int end, int cnt, vector<pair<string,string>> &v, vector<vector<string>> clothes, set <string> &kind, int standard) {
	if (end == cnt) {
		answer += 1;
		return;
	}
	for (int k = standard; k < clothes.size(); k++) {
		if (!check[k] && kind.count(clothes[k][1]) ==0) {
			check[k] = true;
			kind.insert(clothes[k][1]);
			v.push_back({ clothes[k][0],clothes[k][1] });
			solve(end, cnt + 1, v, clothes, kind,k);
			kind.erase(v[v.size() - 1].second);
			v.pop_back();
			check[k] = false;
		}
	}
}


int solution(vector<vector<string>> clothes) {
	answer = 0;
	int kind_cnt = 0; //종류개수

	set <string> clothes_kind;

	for (int i = 0; i < clothes.size(); i++) {
		clothes_kind.insert(clothes[i][1]);
	}

	for (int k = 1; k <= clothes_kind.size(); k++) {
		vector <pair<string, string>> v;
		set <string> kind;
		memset(check, false, sizeof(check));
		solve(k,0, v, clothes , kind,0);
	}

	return answer;
}