Syureu

찍먹을 좋아하는 사람.

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

2 분 소요

나는야 포켓몬 마스터 이다솜 (https://www.acmicpc.net/problem/1620)

문제 분석

지문의 99%는 필요가 없다.

현재 가지고 있는 포켓몬 도감에서 포켓몬의 이름을 보면 포켓몬의 번호를 말하거나, 포켓몬의 번호를 보면 포켓몬의 이름을 말하는 연습을 하도록 하여라.

분석 끝

접근

포켓몬의 수와 문제의 수가 최대 10만개이다. STL VS COLLECTION 시리즈 1편에서 설명한것처럼 배열스타일로 이 문제를 풀면, 가장 끝에 있는 포켓몬을 10만번 출력 시키라고 하면 인생이 망하는 것이다. 검색과정에 O(logN)의 시간복잡도를 가지는 TreeMap을 사용함으로써 최대 10만+log2(10만) 의 연산량으로 답을 내도록 하자. 이 문제는 그냥 맵의 사용만 유도하는 문제라 사실 TreeMap일 필요가 없다. 해시맵으로도 가능하고, 해시 충돌이 없을경우 훨씬 빠르다.

1. 이름을 받아 맵에 저장

map<string, int> simap;

for (int i = 1; i <= n; ++i) {
    cin >> str;
    simap[str] = i;
}

입력되는대로 1번 2번… 순이라고 하였으니 위와 같이 셋팅한다.

2. 쿼리

이후의 M개의 줄에

입력으로 숫자가 들어왔다면 그 숫자에 해당하는 포켓몬의 이름을, 문자가 들어왔으면 그 포켓몬의 이름에 해당하는 번호를 출력하면 돼. 라고 한다.

우리는 맵에 string:int 쌍을 저장했기 때문에 이름을 물어봤을때 번호를 답해주기는 쉽다.

cin >> str;

if (s[0] < '0' && '9' < s[0]) { // 첫 글자가 숫자 범위가 아니면
    cout << simap[str] << '\n';
}

그런데 번호를 물어봤을때 이름을 답하는 과정은 어떻게 처리할까? 지금대로라면 int:string 쌍의 정보도 없고 트리맵의 구조상 value로 find를 할 수가 없다.
그러므로 처음 입력받을때 int:string인 맵도 같이 만들어주자.

map<string, int> simap;
map<int, string> ismap;

for (int i = 1; i <= n; ++i) {
    cin >> str;
    simap[str] = i;
    ismap[i] = str;
}

마치 양방향 그래프 같은 느낌이다. 이렇게 하면 우리는 이제 번호를 물어봤을 때 포켓몬의 이름 대답도 할 수 있게 되었다.

cin >> str;

if (s[0] < '0' && '9' < s[0]) { // 첫 글자가 숫자 범위가 아니면
    cout << simap[str] << '\n';
}
else { // 첫 글자가 숫자 범위이면
    cout << ismap[stoi(str)] << '\n';
}

C++ 소스

#include<iostream>
#include<map>
#include<string>
using namespace std;
int n, m;
string str;
map<string, int>simap;
map<int, string>ismap;
int main() {
	cin.sync_with_stdio(0); cin.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= n; ++i) {
		cin >> str;
		simap[str] = i;
		ismap[i] = str;
	}
	while (m--) {
		cin >> str;
		if (str[0] < '0' || str[0] > '9') { // 첫 글자가 숫자 범위가 아니면
			cout << simap[str] << '\n';
		}
		else { // 첫 글자가 숫자 범위이면
			cout << ismap[stoi(str)] << '\n';
		}
	}
}

Java 소스

import java.io.*;
import java.util.*;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		StringBuilder sb = new StringBuilder();
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		Map<String, Integer> simap = new TreeMap<>();
		Map<Integer, String> ismap = new TreeMap<>();
		for (int i = 1; i <= n; ++i) {
			String str = br.readLine();
			simap.put(str, i);
			ismap.put(i, str);
		}
		for (int i = 0; i < m; ++i) {
			String str = br.readLine();
			if (str.charAt(0) < '0' || str.charAt(0) > '9') { // 첫 글자가 숫자 범위가 아니면
				sb.append(simap.get(str));
			} else { // 첫 글자가 숫자 범위이면
				sb.append(ismap.get(Integer.parseInt(str)));
			}
			sb.append("\n");
		}
		System.out.println(sb);
	}
}

참고