[프로그래머스] 메뉴리뉴얼 (C++) (2021 KAKAO 기출 )

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

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

레벨 : Level 2

2021 KAKAO BLIND RECRUITMENT에 나왔던 문제이다. 

 

배열의 크기가 각각 20,10이하로 제한되어 있기 때문에 완전탐색으로 구현이 가능한 문제였다.

이 문제의 핵심은 map 자료형을 이용하는 것이다. 

평소에 vector만 거의 써왔기 때문에, map을 자주 써보지않아 익숙치 않았고 이 때문에 내장함수들을 찾아서 썻다. 

map도 매우 유용한 자료구조 이기 때문에 꼭 알아두자!!

---

맵(Map)
노드 기반 이진 트리 구조로 {key, value} 쌍으로 구성되어 있다. #include<map>을 헤더에 추가해야하며, 삽입시 오름차순으로 자동 정렬된다. 

 

유용한 기능

• 생성자 : map<자료형, 자료형> [변수이름]m;
• 삽입 : m.insert(make_pair<자료형,자료형>(값,값));
• 삽입 or 수정 : m[key] = val로 추가나 수정 가능
• 삭제 : m.erase(key) : 해당 원소 삭제
• 지우기 : m.clear()
• 탐색 : for(auto it = m.begin(); it!=m.end(); it++){ m->first << m->second }
• m.count(key) : key값에 해당하는 원소 개수 반환
• 벡터로 복사 : vector<pair<string,int>> v(m.begin(),m.end())
• m.find(key) : key 값에 해당하는 iterator 반환
  • 해당 key값이 존재하지 않으면 m.end()를 반환
  • if(m.find(key)!=m.end()) 이런식으로 사용가능

---

문제 풀이 방식

1. 현재 코스수가 M이라면 M개를 선택해서 만들수있는 모든 코스요리 후보를 map<string,int>에 넣는다. 이 때, Key 값은 코스요리고 Value값은 해당 코스요리가 선택된 경우이다. 

2. map을 vector로 복사 후, vector에서 int를 기준으로 내림차순 정렬한다.

3. int가 2이상이면 최대 int에 해당하는 string들을 result 벡터에 넣는다.

4. 모든 코스수에 대해 반복 한다.

5. result벡터를 오름차순 정렬한다.

 

추가적으로, m[tmp]++은 tmp라는 key가 존재한다면 기존 value값에 1을 더해주고, key가 존재하지 않는다면 m[tmp]=1를 만들어준다.

 

전체코드는 아래와 같다.

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

map<string, int> m; //<조합,선택수> : 코스요리 후보

void Course(string original, string tmp, int index,int size) {//size만큼 뽑기
	if (tmp.size() == size) m[tmp]++;
	
	for (int i = index; i < original.size(); i++){
		Course(original, tmp + original[i], i + 1, size);
	}
}

bool compare(pair<string, int> a, pair<string, int> b) { //선택수 내림차순 
	return a.second > b.second;
}
vector<string> solution(vector<string> orders, vector<int> course) {
    vector<string> answer;
	for (int i = 0; i < course.size(); i++){
		int size = course[i]; //현재 코스수
		m.clear();
		for (int j = 0; j < orders.size(); j++){
			sort(orders[j].begin(), orders[j].end());
			if(size<=orders[j].size()) Course(orders[j],"", 0,size);
		}
		if (m.size() == 0) continue; //가능한 조합 없는경우
		vector<pair<string, int>> v (m.begin(), m.end()); //map->vector로 복사
		sort(v.begin(), v.end(), compare);
		int largest = v[0].second;//제일 많이 선택된 횟수
		if (largest >= 2) { //최소 2번이상
			for (int j = 0; j < v.size(); j++) {
				if (largest == v[j].second) answer.push_back(v[j].first);
				else break;
			}
		}
	}
	sort(answer.begin(), answer.end());
    return answer;
}