프로그래머스 2023.06.16 (1Lv 달리기 경주)

프로그래머스

문제

---

코딩

---

#include <string>
#include <vector>
#include <map>

using namespace std;

vector<string> solution(vector<string> players, vector<string> callings) {
	vector<string> answer;
	map<int, string> mapRank;
	map<string, int> mapPlayers;
	for (size_t i = 0; i < players.size(); ++i)
	{
		mapPlayers.insert(make_pair(players[i], i));
		mapRank.insert(make_pair(i, players[i]));
	}

	for (size_t i = 0; i < callings.size(); ++i)
	{
		int icur_rank = mapPlayers.find(callings[i])->second;
		string strFst = mapRank.find(icur_rank - 1)->second;
		string strSec = mapRank.find(icur_rank)->second;
		mapRank.find(icur_rank - 1)->second = strSec;
		mapRank.find(icur_rank)->second = strFst;
		mapPlayers.find(strSec)->second = icur_rank - 1;
		mapPlayers.find(strFst)->second = icur_rank;
	}

	map<int, string>::iterator iter = mapRank.begin();
	for (; iter != mapRank.end(); ++iter)
	{
		answer.push_back(iter->second);
	}

	return answer;
}

처음 구현했던 코드는 map을 사용하지 않고, 이중 for문을 사용해 풀었었다. (callings[i]를 players에서 찾아서 이전 idx 요소와 서로 바꿔주는 방식이었다.)

하지만 몇 몇 테스트 상황에서는 수행하는 시간이 너무 길어져 실패했었다. (Players가 50000개 까지 주어질 수 있고, Callings 또한 100000개가 주어질 수 있기 때문에 이중 for문을 사용하게 되면 O(n^2)으로 시간이 길어질 수 있다.)

따라서 map을 이용해 키값으로 빠르게 찾아 서로 바꿔주도록 구현했다.

즉, map을 이용해 탐색시간을 줄이는 것이 중요했던 문제같다.

실행 결과

---