문제

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

핵심

• 입력의 크기가 $10^6$이라 대략 $O(N\times\log_2N)$ 이하의 알고리즘을 사용한다.
• 포켓몬 이름이 주어지면 번호를 답하고 포켓몬 번호가 주어지면 포켓몬 이름을 답해야 한다. 따라서 포켓몬 이름과 그에 맞는 번호를 저장하는 해시 자료구조를 사용하고, 번호에 대한 포켓몬 이름을 답하기 위해 문자열 배열을 사용한다.
• 해시 자료구조로는 C++에선 unordered_map, Java에선 HashMap을 사용한다.

코드

시간복잡도

• $O(N)$

C++

#include <iostream>
#include <unordered_map>
#include <string>
using namespace std;

string i2s[100'004];
unordered_map<string, int> s2i;
int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= n; ++i) {
		string name;
		cin >> name;
		i2s[i] = name;
		s2i[name] = i;	
	}
	for (int i = 1; i <= m; ++i) {
		string key;
		cin >> key;
		if (key[0] >= '0' && key[0] <= '9') {
			int num = stoi(key);
			cout << i2s[num] << '\n';
		}
		else {
			cout << s2i[key] << '\n';
		}
	}
}

Java

import java.io.*;
import java.util.HashMap;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        String[] i2s = new String[n + 4];
        HashMap<String, Integer> s2i = new HashMap<>();
        for (int i = 1; i <= n; i++) {
            String name = br.readLine();
            i2s[i] = name;
            s2i.put(name, i);
        }
        for (int i = 0; i < m; i++) {
            String q = br.readLine();
            if (q.charAt(0) >= '1' && q.charAt(0) <= '9')
                bw.write(i2s[Integer.parseInt(q)] + "\n");
            else
                bw.write(s2i.get(q) + "\n");
        }
        bw.flush();
        bw.close();
        br.close();
    }
}