[C++] 백준 1620번 find()

어떤 문제를 풀기 위해서 새롭게 배우는 개념들에 대해,
그 문제를 풀 수 있을 만큼만 알고 있어서 문제라고 생각했는데
계속 풀면서 계속 새로 배우면 되지 싶다 ~

1620. 나는야 포켓몬 마스터 이다솜

n개의 포켓몬 도감이 주어지고 m개의 숫자 혹은 문자로 된 문제가 주어진다.
문제가 숫자이면 도감의 숫자 번째 포켓몬을 출력하고
문제가 문자이면 도감에서 해당 포켓몬이 몇 번째인지 출력한다.

풀이

처음에는 vector<string> v에 담아서 숫자면 v[숫자-1],
문자면 find(v.begin(), v.end(), 문자) 해서 풀었는데
find를 못찾는다는 컴파일 에러가 뜨는 거다.

알고 보니까 find를 쓰려면 algorithm을 include 해줘야 하는데
visual studio code에서 에러가 나지 않았던 이유는
다른 헤더가 algorithm을 포함하고 있었을 수도 있다는 걸 알았다.
싱기

헤더에 포함해주고 다시 냈는데 이번엔 시간 초과가 난다.
그러면 정렬을 하고 binary_search를 써야것군 생각했는데
binary search는 값의 유무만 알 수 있다.

그러면 index 값과 name을 vector 말고 map에 넣어두고 찾으면 쓰겄다.
again 시간 초과
ㅇㄴ

map의 key로 value를 찾는 건 금방인데 value로 key를 찾을 때가 문젠가 싶어
문제가 숫자인 경우는 vector<string>에서 찾고,
문자인 경우를 만들어둔 map에서 찾도록 수정했다.

해결 ~

코드

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

using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int n, m;
	cin >> n >> m;

	map<string, int> pom;
	vector<string> pov;
	string str;
	for (int i = 1; i <= n; i++) {
		cin >> str;
		pom[str] = i;
		pov.push_back(str);
	}

	for (int i = 0; i < m; i++) {
		cin >> str;
		if (isdigit(str[0])) {
			cout << pov[stoi(str) - 1] << "\n";
		}
		else {
			cout << pom.find(str)->second << "\n";
		}
	}

	return 0;
}

find()

vector랑 map을 같이 쓰면서 헷갈렸던 부분이 find이다.
m.find(찾는값)도 쓰고 find(v.begin(), v.end(), 찾는값)도 쓴다.
언제 어떤 자료구조에 사용할 수 있는지 간단히 정리해보자.

?.find(찾는값)

1. 사용 가능한 자료구조

• 주로 연관 컨테이너(associative containers) 에서 사용된다.
• ex) map, set, unordered_map, unordered_set, string

2. 동작

• 컨테이너 내부에 특정 키 또는 값이 존재하는지 찾는다.
• 연관 컨테이너에서는 키에 대한 탐색이 빠르다(로그 또는 상수 시간).

3. 반환값

• 연관 컨테이너: 있으면 iterator, 없으면 ?.end().
• 문자열: 있으면 인덱스, 없으면 std::string::npos.

find(?.begin(), ?.end(), 찾는값)

1. 사용 가능한 자료구조

• 모든 순차 컨테이너(sequence containers) 에서 사용할 수 있다.
• 연관 컨테이너에서도 사용 가능하지만, 비효율적이다.
• ex) vector, deque, list, array 등

2. 동작

• 선형 탐색으로 첫 번째로 일치하는 요소를 찾는다.
• 시간 복잡도: O(n)

3. 반환값

• 있으면 iterator, 없으면 ?.end().