백준 1620번 : 나는야 포켓몬 마스터 이다솜

문제 링크 : www.acmicpc.net/problem/1620

내 풀이(2021.1.21.) : 

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>

using namespace std;

string unsorted[100000];
vector<pair<string,int>> sorted[26];

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N, M; cin >> N >> M;
	for (int i = 0; i < N; i++) {
		cin >> unsorted[i];
		sorted[unsorted[i][0]-'A'].push_back(make_pair(unsorted[i],i));
	}

	for (int i = 0; i < M; i++) {
		string temp; cin >> temp;
		if (temp[0] >= '0' && temp[0] <= '9') {
			printf("%s\n", unsorted[stoi(temp) - 1].c_str());
		}
		else {
			vector<pair<string, int>>& v = sorted[temp[0] - 'A'];
			for (int j = 0; j < v.size(); j++) {
				if (v[j].first == temp) {
					printf("%d\n", v[j].second + 1);
					break;
				}
			}
		}
	}

	return 0;
}

O(N^2)이면 최대 100초의 복잡도가 나오므로

탐색 속도를 개선하기 위해

단어의 첫 글자를 기준으로 26개의 벡터에 나누어 저장하였다.

---

다른 풀이1 : '이분 탐색'를 활용하여 O(N)을 O(logN)로 줄일 수 있다.

참고 : j3sung.tistory.com/512

---

다른 풀이2 : STL의 map을 사용한다.

참고 : hyeonnii.tistory.com/202

#include <iostream>
#include <string>
#include <map>
#include <cctype>

using namespace std;

map<int, string> get_by_int;
map<string, int> get_by_string;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N, M; cin >> N >> M;
	for (int i = 0; i < N; i++) {
		string temp; cin >> temp;
		get_by_int[i + 1] = temp;
		get_by_string[temp] = i + 1;
	}

	for (int i = 0; i < M; i++) {
		string temp_str; cin >> temp_str;
		if (isdigit(temp_str[0])) printf("%s\n", get_by_int[stoi(temp_str)].c_str());
		else printf("%d\n", get_by_string[temp_str]);
	}

	return 0;
}

- printf("%s\n", str.c_str()); 에서 str가 string 타입이면 .c_str()를 통해 const char* 타입으로 변경해주어야 제대로 출력된다는 것 주의

- isdigit()은 <cctype>이라는 헤더파일을 이용해 char값이 숫자인지 아닌지 판단 : int isdigit(int c);

  즉, c가 '0'~'9' 사이의 아스키 코드이면 0이 아닌 값 리턴, 그렇지 않으면 0 리턴.

- Map을 사용해서 검색하므로 O(N)을 O(logN)로 줄일 수 있음

---

C++ STL의 Map 컨테이너 특징
 * key, value 쌍으로 저장 - key에는 primitive type(int, long, char, double) 모두가 들어갈 수 있음
 * key 중복 불가 - multimap으로 key 중복 가능
 * 균형이진탐색트리(AVL트리) 구조 - 삽입/삭제 시마다 정렬 수행 : O(logN)
 * 검색 속도 : O(logN)