c++
프로그래머스 가장 많이 받은 선물
시코.
2024. 3. 5. 17:33
728x90
데이터는 일단 해시테이블로 선택했다
문자열을 그대로 키로 지정도 할 수 있고 접근도 빠를것 같아서였다
transfer_present_count
해시테이블에 주고받은 한 거래 "준사람 받은사람"의 형태를 그대로 키로 넣고 값은 몇번 그게 발생을 했는지로 저장했다.
present_index
선물 지수와 관련된 해시테이블이다 거래를 카운팅할때 거래를 반으로 갈라 왼쪽에있으면 준사람을 키로 찾아 선물지수를 적절히 계산해주었다.
current_present
최종적으로 받는 선물을 계산해서 이름을 키로 값은 선물 받을 갯수로 해시테이블에 넣었다.
해시테이블 구조로 최종값을 받았기때문에 추가적으로
키를 값데이터를 비교해 정렬해 주었다
하지만 그냥 최대값을 찾아서 그 키값 저장했다 반환하는게 더 빠를것 같다.문자열 가르는 split 함수는 C++에 없어서
https://www.lifencoding.com/language/22?p=1
[C++] string타입 문자열을 split하기
Java에서는 문자열을 특정 구분자를 이용하여 여러 부분으로 나누는 함수 split을 제공한다. 또한 C의 경우 strtok라는 함수를 이용하여 char배열 형태의 문자열을 구분자를 기준으로 나눌 수 있다.
www.lifencoding.com
이런방법 써도 좋을것 같다.
#include <algorithm>
#include <string>
#include <vector>
#include <unordered_map>
std::unordered_map<std::string, long long> transfer_present_count;//선물을 준 거래를 카운팅
std::unordered_map<std::string, long long> present_index;//선물지수
std::unordered_map<std::string, long long> current_present;//지금줘야하는 선물
//인덱스만 정렬하기위해 값을 찾아 비교하는 함수 https://iamaman.tistory.com/788 여기 참고함
bool comparator(const std::string& l, const std::string& r)
{
return current_present[l] > current_present[r];
}
int solution(std::vector<std::string> friends, std::vector<std::string> gifts) {
int answer = 0;
//선물 거래를 카운팅하고 그후 반으로 갈라 선물지수를 계산한다.
for (auto gift_i = gifts.begin(); gift_i != gifts.end(); gift_i++)
{
if(transfer_present_count.find(*gift_i) != transfer_present_count.end())
transfer_present_count[*gift_i]++;
else
transfer_present_count[*gift_i] = 1;
auto space_found = std::find(gift_i->begin(),gift_i->end(),' ');
int found_index = space_found - gift_i->begin();
std::string left = gift_i->substr(0, found_index);
std::string right = gift_i->substr(found_index + 1, gift_i->size() - 1 );
present_index[left]++;
present_index[right]--;
}
//선물을 누가 더 많이 줬거나 같으면 누가 더 선물지수가 높은지 전부 비교하고 선물 받아야할때만 카운팅
for (auto friends_i_first = friends.begin(); friends_i_first < friends.end(); friends_i_first++)
{
for (auto friends_i_second = friends.begin(); friends_i_second < friends.end(); friends_i_second++)
{
std::string l_key = *friends_i_first;
std::string r_key = *friends_i_second;
if(l_key == r_key)
continue;
std::string l_to_r = (l_key) + ' ' + (r_key);
std::string r_to_l = (r_key) + ' ' + (l_key);
int l;
int r;
//서로 주고받은 수를 l과 r에 할당
if(transfer_present_count.find(l_to_r) != transfer_present_count.end())
l = transfer_present_count[l_to_r];
else
l = 0;
if(transfer_present_count.find(r_to_l) != transfer_present_count.end())
r = transfer_present_count[r_to_l];
else
r = 0;
//내가 준게 더 많으면 선물 받고 같으면 선물 지수로 비교
if(l > r)
{
if(current_present.find(l_key) != current_present.end())
r = current_present[l_key]++;
else
current_present[l_key] = 1;
}
else if(l == r)
{
if(present_index[l_key] > present_index[r_key])
{
if(current_present.find(l_key) != current_present.end())
r = current_present[l_key]++;
else
current_present[l_key] = 1;
}
}
}
}
//이제 인덱스 받아서 정렬 하자
std::vector<std::string> sort_key_by_gift(friends);
std::sort(sort_key_by_gift.begin(), sort_key_by_gift.end(),comparator);
return current_present[sort_key_by_gift[0]];
}
int main()
{
std::vector<std::string> ex1 = {"muzi", "ryan", "frodo", "neo"};
std::vector<std::string> ex2 = {"muzi frodo", "muzi frodo", "ryan muzi", "ryan muzi", "ryan muzi", "frodo muzi", "frodo ryan", "neo muzi"};
solution(ex1,ex2);
return 0;
}
더보기
처음 메모한거 다 적은거
#define _SILENCE_STDEXT_HASH_DEPRECATION_WARNINGS
//이건 그냥 hash_map 잘못써서 썻던거
#include <algorithm>
#include <string>
#include <vector>
#include <unordered_map>
/*
하나의 배열당 좌우로 나눠서 맞아 해시테이블 쓰려고 했었지
가장 많은 선물을 받는 선물의 수를 출력
선물을 더 많이 준 친구가 선물을 받는다
두 사람이랑 비교한다
선물지수는 친구들에게 준 선물 - 받은 선물 수
두사람이 주고받은 수가 같거나 없으면 선물지수 사용
선물 지수마저같으면 주고받지 않는다
해시맵으로 이름을 따라가기는 쉽다
이름별로 숫자를 얻어오는것은쉽다
그럼 그 이름들과 같을 가져와서 값들을 정렬한 뒤
값의 인덱스를 원래 받아왔떤 자료들의 인덱스로어쩌구하는 그거있었는데
인덱스 정렬
그렇게 정렬하면 선물 주고받은 횟수를 알 수 있다
근데 받은 수랑 준 수 모두 기억하고 있어야 한다 선물 지수를 위해
이름을 저장해 놓고 그 이름에 선물 받은 수 선물 준 수
그리고 주고받은 이름에도 서로 얼마나 주고 받았는지
서로를 나타내는 해시맵 두 이름 그대로 쓰고
내가 선물을 주고 선물을 받은 횟수 그러니까 선물 지수를 위한 해시 맵 하나 더 있으면 좋을것 같다
그리고 모든 가능한 주고 받는 해시 값들을 비교할 수 있게 이름들도 배열에 넣어놓자
그리고 이름이 같지 않으면 서로 주고 받은 해시 값을 받아로 수 있게 된다
*/
//이건 안썻음 지우는거 깜빡함 ㅜㅜ생각해보니 선물지수로 인트형 하나만 있어도 되겠다 줘을떄 하나 받았을때 하나
typedef struct Present_Transfer_Count
{
long long gave;
long long taken;
} Present_Transfer_Count;
std::unordered_map<std::string, long long> transfer_present_count;//선물을 준 전체이름의 차운팅
std::unordered_map<std::string, long long> present_index;//선물지수
std::unordered_map<std::string, long long> current_present;//지금줘야하는 선물
bool comparator(const std::string& l, const std::string& r)
{
return current_present[l] > current_present[r];
}
int solution(std::vector<std::string> friends, std::vector<std::string> gifts) {
int answer = 0;
//선울을 준쪽은 선물지수가오르고
//받은쪽은 내려가게
//전체적인 선물 주고받은 기록도 카운팅
for (auto gift_i = gifts.begin(); gift_i != gifts.end(); gift_i++)
{
if(transfer_present_count.find(*gift_i) != transfer_present_count.end())
transfer_present_count[*gift_i]++;
else
transfer_present_count[*gift_i] = 1;
auto space_found = std::find(gift_i->begin(),gift_i->end(),' ');
int found_index = space_found - gift_i->begin();
std::string left = gift_i->substr(0, found_index);
std::string right = gift_i->substr(found_index + 1, gift_i->size() - 1 );
present_index[left]++;
present_index[right]--;
}
//선물을 줘야해 모든 경우의 수를 따져서 선물을 줘야하면
//개어렵당 하나씩 넘어가면서
//한명이지나가고 전부를 구한 후 무언가를 해야하나
//일단 나랑 너일때 바꿔가면서 카운트가 몇인지 알 수 있게ㅔㅆ지
//하지만
///잠깐만 전부 그럴 필요 없이 해쉬테이블을 이용하자
//만약 값이 있는걸 찾았으면 뒤집어서 찾아보고 있으면
//보면되는거고 없ㅇ으면 그냥 주면 되는거지
//근데 아무것도 안준사람들은 어떻게해 그럼 처리가 안되겠네
//이건 보류
//그럼 모든 경우의 수를 계사나고 2를 나눌까?
//중복검사 하기 싫어잉
//중복검사 해야한다면 해쉬에 또 넣을까?
for (auto friends_i_first = friends.begin(); friends_i_first < friends.end(); friends_i_first++)
{
for (auto friends_i_second = friends.begin(); friends_i_second < friends.end(); friends_i_second++)
{
std::string l_key = *friends_i_first;
std::string r_key = *friends_i_second;
if(l_key == r_key)
continue;
std::string l_to_r = (l_key) + ' ' + (r_key);
std::string r_to_l = (r_key) + ' ' + (l_key);
int l;
int r;
//서로 주고받은 수를 l과 r에 할당
if(transfer_present_count.find(l_to_r) != transfer_present_count.end())
l = transfer_present_count[l_to_r];
else
l = 0;
if(transfer_present_count.find(r_to_l) != transfer_present_count.end())
r = transfer_present_count[r_to_l];
else
r = 0;
//내가 준게 더 많으면 선물 받고 같으면 선물 지수로 비교
if(l > r)
{
if(current_present.find(l_key) != current_present.end())
r = current_present[l_key]++;
else
current_present[l_key] = 1;
}
else if(l == r)
{
if(present_index[l_key] > present_index[r_key])
{
if(current_present.find(l_key) != current_present.end())
r = current_present[l_key]++;
else
current_present[l_key] = 1;
}
}
// else
// {
// if(current_present.find(*friends_i_second) != current_present.end())
// r = current_present[*friends_i_second]++;
// else
// current_present[*friends_i_second] = 1;
// }
}
}
//이제 인덱스 받아서 정렬 하자
std::vector<std::string> sort_key_by_gift(friends);
std::sort(sort_key_by_gift.begin(), sort_key_by_gift.end(),comparator);
return current_present[sort_key_by_gift[0]];
}
int main()
{
std::vector<std::string> ex1 = {"muzi", "ryan", "frodo", "neo"};
std::vector<std::string> ex2 = {"muzi frodo", "muzi frodo", "ryan muzi", "ryan muzi", "ryan muzi", "frodo muzi", "frodo ryan", "neo muzi"};
solution(ex1,ex2);
return 0;
}
띄엄띄엄 하긴했는데 한 3일정도 한거 같은데... 처음이라 그런것 같다.
728x90