[C++ 알고리즘] 2021 KAKAO : 메뉴 리뉴얼

 


DFS Brute Force

메뉴 리뉴얼

풀이과정

내가 수행한 전체 Process는 다음과 같다.

  1. 메뉴 조합 구하기
  2. 요리 n개의 코스 중 가장 많이 주문된 것들 구하기
  3. answer에 추가 후 정렬

1번은 손님들이 주문한 전체 메뉴들 중 DFS를 이용해 nCm의 조합을 구했다. 코스(조합)를 구한 후에는 각 코스가 손님들에게서 주문된 적 있는지 검사 후 최댓값을 추출하였다. 풀면서 BOJ 복면산 문제가 생각이 나서 비슷하게 풀었는데, 다른 풀이를 보니 나는 너무 복잡하게 푼 것 같다 ㅠㅅㅠ.. map을 이용해서 풀 수도 있고 전역변수를 쓸데없이 많이 선언하지 않고 매개변수에 string을 넣어서 푸는 방법도 있었다. 다음엔 더 깔끔하게 풀 수 있도록 노력해야지😭


코드

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

using namespace std;

bool isAlphabetExist[26] = {false,};
vector<char> alphabetArray;
vector<bool> isAlphabetChecked;
char selectedCourse[11];
vector<string> tempAnswer;
int tempMax = 0;

int counting_menu(vector<string> orders, int limit) {
	int cnt = 0;
	for (int i = 0; i < orders.size(); i++) {
		int j;
		for (j = 0; j < limit; j++) {
			if (orders[i].find(selectedCourse[j]) == string::npos) break;
		}
		//조합 있는경우
		if (j == limit) cnt++;
	}
	return cnt;
}

void dfs(vector<string> orders, int level, int pos, int limit) {
	if (level == limit) {
		// 각 조합에 대해 몇번 나왔는지 세기
		int res = counting_menu(orders, limit);
		if (tempMax <= res) {
			if (tempMax < res) {
				tempMax = res;
				tempAnswer.clear();
			}
			string combination = "";
			for (int i = 0; i < level; i++)
				combination += selectedCourse[i];
			tempAnswer.push_back(combination);
		}
	}
	else {
		for (int i = pos; i < isAlphabetChecked.size(); i++) {
			if (!isAlphabetChecked[i]) {
				isAlphabetChecked[i] = true;
				selectedCourse[level] = alphabetArray[i];
				dfs(orders, level+1, i+1, limit);
				isAlphabetChecked[i] = false;
			}
		}
	}
}

vector<string> solution(vector<string> orders, vector<int> course) {
    vector<string> answer;

	// 1. 출현한 알파벳 구하기
	for (int i = 0; i < orders.size(); i++) {
		for (int j = 0; j < orders[i].size(); j++) {
			int ind = orders[i][j] - 'A';
			isAlphabetExist[ind] = true;
		}
	}

	// 2. 존재하는 알파벳만 추출하기
	for (int i = 0; i < 26; i++) {
		if (isAlphabetExist[i]) {
			alphabetArray.push_back(i + 'A');
			isAlphabetChecked.push_back(false);
		}
	}

	// 3. 각 n개의 코스에 대해 solution
	for (int i = 0; i < course.size(); i++) {
		for (int j = 0; j < isAlphabetChecked.size(); j++) {
			isAlphabetChecked[j] = false;
		}

		// 4. 조합 구하기
		tempAnswer.clear();
		tempMax = 2;
		dfs(orders, 0, 0, course[i]);

		for (int j = 0; j < tempAnswer.size(); j++) {
			answer.push_back(tempAnswer[j]);
		}
	}

  // 5. 정렬
	sort(answer.begin(), answer.end());

    return answer;
}

결과

테스트 1 〉	통과 (0.18ms, 3.91MB)
테스트 2 〉	통과 (0.12ms, 3.95MB)
테스트 3 〉	통과 (0.06ms, 3.91MB)
테스트 4 〉	통과 (0.12ms, 3.94MB)
테스트 5 〉	통과 (0.14ms, 3.94MB)
테스트 6 〉	통과 (0.23ms, 3.94MB)
테스트 7 〉	통과 (0.23ms, 3.92MB)
테스트 8 〉	통과 (0.97ms, 3.93MB)
테스트 9 〉	통과 (2.65ms, 3.94MB)
테스트 10 〉	통과 (41.07ms, 3.94MB)
테스트 11 〉	통과 (26.88ms, 3.97MB)
테스트 12 〉	통과 (39.37ms, 3.93MB)
테스트 13 〉	통과 (4096.20ms, 3.96MB)
테스트 14 〉	통과 (5098.76ms, 3.93MB)
테스트 15 〉	통과 (2043.62ms, 3.98MB)
테스트 16 〉	통과 (1.91ms, 3.94MB)
테스트 17 〉	통과 (19.09ms, 3.94MB)
테스트 18 〉	통과 (13.00ms, 3.72MB)
테스트 19 〉	통과 (0.80ms, 3.94MB)
테스트 20 〉	통과 (2.76ms, 3.94MB)


:bookmark: REFERENCE
[프로그래머스] 메뉴 리뉴얼 문제 풀이 (2021 카카오 코딩테스트)