[PS]2021 KAKAO BLIND RECRUITMENT 2021 : 메뉴 리뉴얼

programmers.co.kr/learn/courses/30/lessons/72411

 

코딩테스트 연습 - 메뉴 리뉴얼

문제 설명

손님들이 시키는 메뉴가 문자열로 주어진다. 이때 문자열의 알파벳 하나가 메뉴 하나이다.

이렇게 시킨 메뉴들에서 세트 메뉴를 만들려고 한다.

문제에서 주어진 조건을 만족하고, 많이 나타난 메뉴 조합들로 세트 메뉴를 구하는 문제이다.

 

문제 풀이

간단하게 요약하자면, 주어진 문자열에서 가능한 모든 조합을 생성, 많이 등장한 순으로 가져오면 해결할 수 있다.

 

예를 들어, 주문으로 ABC가 들어올 경우 가능한 모든 조합인

A, B, C, AB, AC, BC, ABC 를 후보로 생각할 수 있고, 모든 주문들에 대해 이를 수행, 많이 등장한 후보들을 가져온다!

 

하지만 여기에 몇몇 제약이 있는데 다음과 같다.

• 2번 이상 등장한 조합만이 세트 메뉴로 선택 가능
• 같은 길이의 조합이 여러 개 있다면, 그 중에 가장 많이 등장한 조합을 선택한다.
• WX, XW 처럼 정렬해서 같은 조합은 서로 같은 조합으로 취급함.
• 문제에서 지정한 길이의 조합만을 세트 메뉴로 선택할 수 있다.

이러한 제약 조건에 대한 처리를 여러개 해줘서 구현할 수 있다.

 ex) (조합, 등장 횟수) map 사용, 문자열 정렬, 길이별 최대 등장횟수 체크 등등

 

소스 코드

 

#include<string>
#include<map>
#include<vector>
#include<algorithm>
#include<cstring>
using namespace std;

bool check[15];
map<string, int> combination; //가능한 조합 목록
int maxLength[50]; //길이 n 짜리 특정 조합에 대해 몇 번이 최대로 생겼는지

bool compare(const pair<string, int> &a, const pair<string, int> &b) {
	if (a.second == b.second) {
		return a.first < b.first;
	}
	else {
		return a.second > b.second;
	}
}
void powerSet(int index, string alpha, vector<int> course) { 
	int num = alpha.length();
	if (index == num) { //끝까지 봤음
		string temp;
		int count = 0;
		for (int i = 0; i < num; i++) {
			if (check[i]) {
				temp.push_back(alpha[i]);
				count++;
			}
		}
		//count 가 course 에 포함되는 값인지 봐야함
		bool flag = false;
		for (auto lim : course) {
			if (count == lim) {
				flag = true;
				break;
			}
		}
		if (flag) { //생성해도 문제 없다!
			int L = temp.length();
			combination[temp]++;
			maxLength[L] = (maxLength[L] < combination[temp] )? combination[temp] : maxLength[L]; 
		}
	}
	else {
		check[index] = true;
		powerSet(index + 1, alpha, course);
		check[index] = false;
		powerSet(index + 1, alpha, course);
	}
}
vector<string> solution(vector<string> orders, vector<int> course) {
	vector<string> answer;
	for (auto alpha : orders) {
		sort(alpha.begin(), alpha.end()); //중복 방지 위해 입력 문자열 사전순 정렬
		memset(check, 0, sizeof(check));
		powerSet(0, alpha, course);
	}
	vector<pair<string, int>> mp(combination.begin(), combination.end());
	sort(mp.begin(), mp.end(), compare);
	for (auto alpha : mp) {
		int c = alpha.second;
		if (c >= 2) { // 등장 횟수가 2번 이상
			int L = alpha.first.length();
			if (maxLength[L] == c) {
				answer.push_back(alpha.first);
			}
		}
		else {
			break;
		}
	}
	sort(answer.begin(), answer.end());
	return answer;
}

github.com/onaeonae1/ProblemSolving/blob/master/KAKAO_BLIND_2021/%EB%A9%94%EB%89%B4%20%EB%A6%AC%EB%89%B4%EC%96%BC.cpp

onaeonae1/ProblemSolving

 

배운 점

• 문자열에서 가능한 모든 조합을 생성할 때 멱집합에 대해서 공부했다.
• map은 기본적으로 (key, value) 중 key를 기준으로 insert, delete 될 때 정렬된다. (red-black tree 기반이라)
• value 기준으로 정렬해주기 위해서 compare 따로 만들고, vector<pair<string, int>> 로 가져다가 정렬했다.

느낀 점

• 특정 길이의 조합 중 가장 많이 등장한 것만 사용한다. 라는 간단한 내용을 문제를 읽고 바로 이해하지 못했다.
• 요즘 코테 문제들을 잘 못풀고 재미가 없었는데, 엄청 재밌게 매달렸던 것 같다. 그만큼 오래 풀었지만.
• map은 정말정말 매력적인 자료구조 같다. 학교 수업 시간에 이걸 알았어야 하는데 지금이라도 깨달아 다행이다.