접근 방법
1) 완전탐색 -> 인덱스를 이용해 dfs로 접근하자!
2) course에 따라 매핑된 것들 중 가장 많이 주문된거이므로
모든 사람들을 dfs돌리면서 매핑 카운팅을 하자.
코딩 중 중간 점검 및 풀이 과정
예시 1번에서 AC의 갯수가 4개이므로 중간 점검할 필요가 잇다.
-> 확인 결과
: 테스트 1번과 2번의 입력값들 중 AC를 확인하면 올바르다는 것을 확인할 수 있다.
최대값을 갱신하기 위해서 배열로 만들어주고, 모든 mapping값을 돌리면서 확인하자.
-
최대값 갱신하기
-
mapping값 모두 참조하는 방법은
for(auto iter : m) 을 사용하자.
-
확인 결과
-> 얼추 비슷하지만, 정렬하고, 올바르지 못한거 예외처리해야 한다. -
정렬했을떄
-> 테스트 2번과 테스트 3번을 통해서
1) dfs 함수에서 뭔가 예외처리를 해야할까?
2) 아니면 answer삽입 쪽 예외처리가 필요함을 느꼇다. -
문제의 조건에서 최소 2명이상의 사람이 주문을 해야하므로 이를 예외처리하자.
-> 생각좀... -
WX값이 2가 나와야 하는데 1이 나온다..
-> 정렬이 안된건가??? 위에부분 모두 주석 처리하고, 점검해보자!
-> 정렬이 안된것을 확인할수 있다.
=> 수정하자... -
정렬부분을 수정했다.
: 전체가 아니라 글자를 정렬시키는 것이다.
-> 결과
-
최종 결과!!
//=======================================================//
풀이전략
-
입력값들을 정렬해야 하는 이유는 출력값이 정려되어 있고,
조합(재귀)으로 접근할때에는 나열되어 잇는 순으로 값을 나열하기 때문에
정렬을 반드시 해야한다. -
조합으로 코스요리를 map에다가 넣어주면서 cnt수를 증가해준다.
cnt수를 증가하면서 가장 많이 일치하는 코스요리를 픽해서 answer에다가 삽입해야 한다. -
mapping 하는 조건식 중요
-
위와는 다르게 이런식으로 작성했는데,
이렇게 하면 dfs가 종료안되는 문제가 있어서, 고심좀 해야한다.
중요한점 : dfs의 종료 조건을 생각하면서 코드를 작성하자.
위의 dfs의 종료 조건으로는 추가 인덱스와 length의 길이를 비교해서
종료를 하려고 하므로, 문자를 붙이는 것을 dfs 함수호출할때 해야 한다!
주의할점.
-
반드시 pos >= word.lenght() 이후에 map에다가 추가해야 한다.
왜냐하면 선택되지 않은 인덱스도 포함을 해야하기 때문이다.
무슨 말이냐면...
첫번째 사다리를 보면 c-d 에서 바로 mapping을 하게 되면
cde에서 cd의 순열값은 총 2번이다. 경우의 수는 1번 나오지만,
c(사용) - d(사용) -> + 1
c(사용) - d(사용) - e(사용하지 않음) -> + 1
이렇게 되지만 반드시 mapping할때는 마지막 까지 도달한 후에 계산해야 한다. -
문제에서 보면 course의 수에 따라서 mapping값이 나열됨을 확인할 수 있다.
뭔소리냐면 course가 2이면 table[2] 의 값은 2개의 코스 요리를 선택한 사람들의 수를 나타낸다. (cd, 3) , (ac, 4) 이런식으로.
mapping을 왜 배열로 해야 하는지 의문이 들었는데, course의 값과 비교하는 값 중에서 가장 큰값을 찾는데 편하기 때문이다.
만약에 배열로 사용안하면 mapping에 모든 2개로 이루어진 단품, 3개로 이루어진 단품 다 뒤썩이기 때문에 찾는데 불편하기 때문이다.
소스코드
#include <string>
#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;
unordered_map<string, int>table[11];
int maxTable[11] = {0};
void dfs(const string& word, int pos, string result)
{
if(pos >= word.length())
{
int len = result.length();
if(len >= 2)
{
table[len][result]++;
maxTable[len] = max(maxTable[len], table[len][result]);
}
return;
}
dfs(word, pos + 1 , result + word[pos] );
dfs(word, pos + 1, result);
}
vector<string> solution(vector<string> orders, vector<int> course) {
vector<string> answer;
for(auto i : orders)
{
sort(i.begin(), i.end());
dfs(i, 0, "");
}
//map에 저장된 친구들 중에서 (AC, 4) (CD, 3) 최대값을 찾아서 max에다가 저장해야 한다.
for(auto i : course)
{
//2,3,4
for(auto iter : table[i])
{
if(iter.second == maxTable[i] && iter.second >= 2)
answer.push_back(iter.first);
}
}
sort(answer.begin(), answer.end());
//answer.push_back(to_string(table[2]["AC"]));
return answer;
}
