[프로그래머스] 메뉴 리뉴얼 / substr, 순열과 조합

문제

입출력 예

 

풀이

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

using namespace std;
map<string, int> hashMap;
//정답 봄
void dfs(int targetnum, string str, string order) {
	if (str.size() == targetnum) {
        hashMap[str] += 1;
        return ;
	}

    for (int i = 0; i < order.size(); i++)
        dfs(targetnum, str+order[i], order.substr(i+1));
    return ;
}

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

    //없으면 오류
    for (string &order : orders)
        sort(order.begin(), order.end());

    
    for(int cur : course){
    	for(string order : orders)
       		dfs(cur, "", order);
        
        int sup = 0;
        for(auto m : hashMap)
            sup = max(sup, m.second);

        for(auto m : hashMap)
            if(sup >= 2 && m.second == sup)
                answer.push_back(m.first);

        hashMap.clear();
    }
    
    
    
    sort(answer.begin(), answer.end());
	return answer;
}

문제를 해결하는데 엄청 헤매었고 그럼에도 해결되지 않아 정답을 참고했다.

 

내가 시도한 해결방법은 dfs를 사용해 조합을 구한 후 그중 많이 주문된 메뉴의 조합을 찾는 것이었는데,

조합을 구하는 과정에서 문제를 제대로 이해하지 못해 해결할 수 없었던 것 같다.

주문된 모든 알파벳을 구한 후 그것을 사용해 조합을 구했고 결과적으로 너무나 많은 조합이 나와 정답에 가까워질 수 없었다.. 😢

 

결국 정답을 보게 되었고, 내가 왜 틀렸는지 알게 되었다!

 

 

 

dfs를 사용하면 순열과 조합을 구할 수 있다.

일단 간단히 정리하고 이부분은 dfs에 더 자세하게 정리하겠다!

DFS - 조합과 순열

 

순열

• 순열이라는 것은 주어진 수열에서 순서에 따라 결과가 달라지는 방식을 의미한다.
• 즉 순열에서 { 1, 2, 3 } 과 { 1, 3, 2 } , { 2, 1, 3 } 은 모두 다른 결과를 가져온다.

조합

• 조합은 순서가 상관이 없는 모임을 의미한다.
• 순서가 상관 없기 때문에 { 1, 2, 3 }, { 1, 3, 2 } , { 2, 1, 3} 모두 같은 것으로 취급을 한다. 

 

여기서는 substr을 활용해 조합을 구했다.

 

substr

문자열. substr(시작 인덱스, 문자열 길이)

• 첫 번째 인자  pos = 시작 인덱스
• 두번쩨인자 count = 문자열 길이
• 문자열의 pos 번째 문자부터 count길이만큼의 문자열을 리턴한다.
• count가 문자열 보다 길다면, 그 이상을 반환하지 않고 문자열의 끝까지만 리턴한다.

문자열. substr(시작 인덱스)

• 첫 번째 인자 pos = 시작 인덱스
• pos부터 원래 문자열의 끝까지 리턴한다.

 

그렇게 구한 조합은 hash map를 사용하여 메뉴와 주문된 횟수를 저장했다.

hash map을 사용하면 key가 String인 데이터를 저장할 때 유용하다!

 

 

생각보다 코드가 간결해서 놀랐다! 그렇게 어려운 문제는 아니었나 보다😥

정답을 모를 땐 너무 끙끙대지 않고 답을 찾아보는 것이 좋을 것 같다...

 

---

[C++ STL] string::substr 사용법 정리 (tistory.com)

[C++ STL] string::substr 사용법 정리

C++ 레퍼런스 - string 의 substr 함수 (modoocode.com)

C++ 레퍼런스 - string 의 substr 함수

[개념] 조합, 순열 + DFS,BFS (tistory.com)

[개념] 조합, 순열 + DFS,BFS