[프로그래머스 Level 2] 메뉴 리뉴얼 (C++)

문제 (https://programmers.co.kr/learn/courses/30/lessons/72411)

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

- 처음 생각 (시간 초과)

orders 반복 -> course 반복 -> course 반복문 내에서 orders 문자열로 next_permutation 돌림

do while문 내에서 orders 문자열을 인덱스 0~j 부분을 잘라준다.

잘라낸 문자열을 정렬하고 set에 존재하는지 확인한다.

set에 해당 문자열이 존재하지 않는다면 set에 삽입, map에 해당 문자열 value 값 증가

 

위 과정을 마치면 map에 정말 많은 수들이 들어있다,,, map을 확인하면서 value 값이 2 이상이면서 해당 문자열 길이 중 최대 value 값인 문자열들을 answer에 삽입했다.

=> 시간이 매우 오래 걸림.... 

 

- 구글링을 통해서 course for문 내의 코드를 변경한 후 통과

tmp라는 vector를 생성하고 false로 초기화한 후 course 값만큼만 true로 설정한다. next_permutaion으로 tmp 벡터를 조합시키고 조합된 벡터 중 true인 인덱스에 위치한 문자들로 문자열을 생성한다. (즉, 인덱스를 조합한 것!)map에 생성된 문자열의 value 값을 증가시켜준다.

 

위 과정을 마치고 정답에 해당하는 값들을 찾기 위해 map을 정렬해야 하는데, value 값을 기준으로 내림차순 정렬을 해야 한다.정렬을 위해 map을 vector로 옮기고 정렬했다.

 

정렬 후 vector를 반복하며 해당 value가 1. 동일한 길이의 문자열 중 최댓값인지, 2. value 값이 2 이상인지 확인한 후 answer에 삽입해주면 끝!

---

[소스코드 - 통과]

	#include <string>
	#include <vector>
	#include <algorithm>
	#include <map>
	using namespace std;
	bool cmp(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;
	map<string, int> m; // 조합, 개수
	for(string i : orders){
	sort(i.begin(), i.end());
	for(int j : course){
	if(i.length() < j) continue;
	vector<bool> tmp(i.length(), true);
	for(int k = 0 ; k < j ; k++) tmp[k] = false;
	do{
	string str;
	for(int k = 0 ; k < tmp.size() ; k++){
	if(!tmp[k]) str += i[k];
	}
	m[str]++;
	}while(next_permutation(tmp.begin(), tmp.end()));
	}
	}
	int arr[course.back() + 1];
	fill(arr, arr + course.back() + 1, 0);
	vector<pair<string, int>> v(m.begin(), m.end()); // map -> vector
	sort(v.begin(), v.end(), cmp);
	for(auto i : v){
	if(i.second >= arr[i.first.length()] && i.second > 1) {
	arr[i.first.length()] = i.second;
	answer.push_back(i.first);
	}
	}
	sort(answer.begin(), answer.end());
	return answer;
	}

view raw 메뉴 리뉴얼.cpp hosted with ❤ by GitHub

[소스코드 - 시간 초과]

	#include <string>
	#include <vector>
	#include <algorithm>
	#include <map>
	#include <set>
	using namespace std;
	bool cmp(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;
	map<string, int> m; // 조합, 개수
	for(string i : orders){
	set<string> s;
	sort(i.begin(), i.end());
	for(int j : course){
	if(i.length() < j) continue;
	do{
	string str = i.substr(0, j);
	sort(str.begin(), str.end()); // ex) ABC, BCA, CBA 모두 같은 값이므로 정렬 후 확인
	if(s.find(str) != s.end()) continue;
	s.insert(str);
	m[str]++;
	}while(next_permutation(i.begin(), i.end()));
	}
	}
	int arr[course.back() + 1];
	fill(arr, arr + course.back() + 1, 0);
	vector<pair<string, int>> v(m.begin(), m.end()); // map -> vector
	sort(v.begin(), v.end(), cmp);
	for(auto i : v){
	if(i.second >= arr[i.first.length()] && i.second > 1) {
	arr[i.first.length()] = i.second;
	answer.push_back(i.first);
	}
	}
	sort(answer.begin(), answer.end());
	return answer;
	}

view raw 메뉴 리뉴얼(fail).cpp hosted with ❤ by GitHub