뚝딱뚝딱

이 문제를 풀려고 했을 당시 처음엔 callings vector에 저장되어 있는 이름들을 players에서 찾아 내야 한다는 생각은 했으나, 이름과 등수를 바로바로 매치할 수 있는 방법이 떠오르지 않아서.. 단순히 while/for 반복문으로 하나씩 접근할 수 밖에 없었다.

그 코드는 아래와 같았고, 역시 몇개의 case에서 시간초과 문제가 발생하였다.

#include <string>
#include <vector>

using namespace std;

vector<string> solution(vector<string> players, vector<string> callings) {

	int sz = players.size();
	int cnt = 1;

	for (int i=0; i<callings.size(); i++){
		string temp = callings[i];

		if (i < callings.size() - 1 && temp == callings[i + 1]) {
			cnt++;
			continue;
		}

		for (int j = 0; j < sz; j++) {
			if (players[j] == temp) {
				int target = j - cnt;
				while (target < j) {
					swap(players[j], players[j - 1]);
					j--;
				}
				cnt = 1;
				break;
			}
		}
	}
	return players;
}

시간 초과가 발생한 부분은 [players를 일일이 탐색하는 부분]+[vector의 위치를 swap하는 부분] 이다. 

vector도 제법 빠른 자료구조라 생각했는데, 자리를 바꾸는 과정은 역시 O(N)이다.

이 문제의 핵심은 map을 사용하는 것이었다!!!!

map을 총 두개 사용하여 해결하였는데, 하나는 등수(int)를 기준으로 이름을 저장한 것과, 하나는 이름(string)을 기준으로 등수를 저장한 것이다.

이렇게 하면 반복문을 돌면서 callings에 있는 이름을 일일이 찾지 않고, 이름 자체를 인덱스로써 활용하여 현재 등수를 알아 낼 수 있다!!

해결한 코드는 아래와 같다.

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

using namespace std;

vector<string> solution(vector<string> players, vector<string> callings) {
	//답 : vector라는 자료구조를 사용하는 것보다 map으로 정렬과정을 거친 후 vector에는 최종 결과 삽입만 하기.

	vector<string> answer;

	int sz = players.size();
	map <int, string> m1;//등수 별 이름 기억해두기
	map <string, int> m2;//이름 별 등수 기억해두기

	for (int i = 0; i<players.size(); i++) {
		m1[i] = players[i];
		m2[players[i]] = i;
	}

	for (int i = 0; i < callings.size(); i++) {
		string temp = callings[i];
		int tempIdx = m2[temp];
		m1[tempIdx] = m1[tempIdx - 1];//swap과정
		m1[tempIdx - 1] = temp;
		m2[temp] = tempIdx - 1;
		m2[m1[tempIdx]] = tempIdx;

	}

	for (auto temp : m1) {
		answer.push_back(temp.second);//m1의 두번째 요소(이름)들을 넣는다.
	}

	return answer;
}

그 결과 map을 활용해서 탐색 시간을 확실히 줄일 수 있었다!!

반환하고자 하는 것은 vector이므로, m1에 등수대로 적힌 이름들을 answer에 push_back하였고 이를 반환하도록 하였다.

1. 'strcpy()' vs '=' / 'assign()' 

c++로 문제를 해결하던 중 string 문자열을 복사하는 코드에서 'strcpy()'를 사용해서 문자열을 대입하려고 했더니, strcpy의 인자인 const char* 타입은 string과 어긋나면서 오류가 발생하였다!

c++에서 string문자열을 복사/대입하려면 std::string의 멤버 함수인 assign() 또는 = 연산자를 사용하면 해결된다!

확실히 c보다 c++은 문자열에서도 제약을 덜 받는 느낌이다,,

2. 'strcmp()' vs '=='

strcmp역시 c언어 스타일에서 사용하는 방식이다. 위에서와 동일한 오류가 발생한다.

c++에서는 단순히 ==을 통해 문자열을 비교할 수 있다!

3.vector의 맨 앞 원소를 삭제할 때

vector.erase(vector.front())

4.vector의 원하는 위치에 원소를 삽입할 때

vector.insert(vector.begin()+i, temp);

인덱스 정보를 넣는 곳에 정수를 입력해서 오류가 발생하였다!

iterator를 인자로 받기 때문에, 위와같이 vector.begin()으로 인덱스 정보를 가져와야 한다.

i는 원하는 인덱스번호라고 생각할 수 있고, temp는 넣고자 하는 값이다.

5. auto 자료형 추론

auto는 변수 선언 시 자료형을 명시하지 않아도, 대입된 값을 통해서 컴파일러가 알아서 자료형을 추론한다.

코드가 간결해지고 유지보수에는 좋으나, 가독성이 떨어질 수 있음!

vector의 기본 쓰임에 대해 복습할 필요가 있음을 느낀 문제..