링크 : https://school.programmers.co.kr/learn/courses/30/lessons/258712
문제 설명
선물을 주고 받은 정보가 있고, 다음과 같은 요구사항이 있을 때, 다음 달 가장 많은 선물을 받는 친구가 받을 선물의 수를 구하시오.
1. 두 사람이 선물을 주고 받은 기록이 있다면, 더 적은 선물을 준 사람이 많이 준 사람에게 다음 달에 선물을 1개 줍니다.
2. 만약 두 사람 사이 선물을 하나도 주고 받지 않았거나 주고 받은 개수가 같다면, 선물 지수가 더 작은 사람이 큰 사람에게 줍니다. * 선물지수 : 이번 달 까지 자신이 친구들에게 준 선물의 수 - 자신이 받은 선물의 수
3. 만약 선물 지수도 같다면 다음 달에 선물을 주고 받지 않습니다.
아이디어
시뮬레이션 문제.
map<string, int> nameIndex : friends 내에 이름 순서대로 Index로 변경용도.
map<string, int> presentIndex : 선물지수 체크용도
vector<vector<int>> swapGifts : 선물 교환 개수 체크용.swapGifts[준사람][받은사람] = 개수
위 3가지를 가지고 교환한 선물 개수와 선물지수를 기록해서 다음 달 선물을 체크해서 정답을 구합니다.
A→B, B→A 2번을 하는 과정을 빼도 좋을 것 같습니다.
코드
#include <bits/stdc++.h>
using namespace std;
vector<string> Split(string str)
{
istringstream iss(str);
string buffer;
vector<string> ret;
while(getline(iss, buffer, ' '))
{
ret.push_back(buffer);
}
return ret;
}
int solution(vector<string> friends, vector<string> gifts) {
map<string, int> nameIndex;
map<string, int> presentIndex;
int cnt = 0;
for(const auto& tmp : friends)
{
nameIndex[tmp] = cnt++;
presentIndex[tmp] = 0;
}
vector<vector<int>> swapGifts(51, vector<int>(51));
for(const auto& gift : gifts)
{
auto A2B = Split(gift);
swapGifts[nameIndex[A2B[0]]][nameIndex[A2B[1]]]++;
presentIndex[A2B[0]]++; presentIndex[A2B[1]]--;
}
vector<int> nextGifts(51, 0);
for(const auto& give : friends)
{
for(const auto& get : friends)
{
if(give == get) continue;
if(swapGifts[nameIndex[give]][nameIndex[get]] > swapGifts[nameIndex[get]][nameIndex[give]])
nextGifts[nameIndex[give]]++;
else if(swapGifts[nameIndex[give]][nameIndex[get]] == swapGifts[nameIndex[get]][nameIndex[give]])
{
if(presentIndex[give] > presentIndex[get])
nextGifts[nameIndex[give]]++;
}
}
}
return *max_element(nextGifts.begin(), nextGifts.end());
}
성능 요약 : 메모리 4.15MB, 시간 2.68ms
'알고리즘' 카테고리의 다른 글
프로그래머스 - 모음사전 (0) | 2024.05.15 |
---|---|
프로그래머스 - 과제 진행하기 (0) | 2024.05.08 |
프로그래머스 - 등산코스 정하기 (0) | 2024.03.16 |
프로그래머스 - n + 1 카드 게임 (0) | 2024.03.13 |
프로그래머스 - 산모양타일링 (0) | 2024.03.11 |