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

 

이 문제를 푸는 방법은 여러가지가 있습니다.

  • bidirectional map (양방향 맵)
  • hash table (해시테이블)
  • Trie (트라이)

그 중 양방향 맵으로 풀면 쉽습니다. key, value를 각각 이름, 번호로 하면 됩니다.

해시 테이블로 풀 때는 hash collision 처리를 잘 해주면 되겠습니다.

// 1620

#pragma GCC optimize ("Ofast")

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;



int main()
{
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
#endif
	
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	
	map<string, int> m1;
	map<int, string> m2;

	int counter = 0;

	int n, m;
	cin >> n >> m;
	while (n--) {
		string s;
		cin >> s;

		++counter;
		m1.emplace(s, counter);
		m2.emplace(counter, s);
	}

	while (m--) {
		string s;
		cin >> s;
		
		if (isdigit(s[0])) {
			int num = stoi(s);
			cout << m2[num] << '\n';
		}
		else {
			cout << m1[s] << '\n';
		}
	}

	return 0;
}

c++에는 bimap을 쓰려면 boost::bimap을 쓰거나 std::map을 두개 쓰는식으로 해야합니다. 앞으로도 STL에 bimap이 추가될 가능성은 낮아 보이네요.

반응형

'Online Judge > 백준' 카테고리의 다른 글

[백준][C++] 2293: 동전 1  (0) 2020.06.14
[백준][C++] 1259: 팰린드롬수  (0) 2020.06.13
[백준][C++] 1550: 16진수  (0) 2020.06.11
[백준][C++] 1012: 유기농 배추  (0) 2020.06.10
[백준][C++] 1010: 다리 놓기  (0) 2020.06.06