키, 값 자료구조 값을 빠르게 찾는 방법 C++ / Java / 파이썬

대표적인 키, 값(밸류) 자료구조인 HashMap에서 Key가 아닌 value로 데이터를 빠르게 찾을 수 있을까요?

 

key를 해쉬하여 사용하기 때문에 해쉬되지 않은 밸류를 찾는것은 매우 어려운 일입니다.

모든 key 쌍을 다 확인해야 합니다.

 

하지만 조건이 적절하면 빠르게 찾는 방법이 있긴합니다.

만일 value가 중복되지 않는다면 

키, 값 을 만들면서 값을 키로, 키를 값으로 한쌍을 더 만드는 것입니다.

 

알고리즘 대회에서 가끔 활용하는 스킬입니다.

적절한 문제인 백준 1620번 나는야 포켓몬 마스터 이다솜을 풀어보면서 확인해 봅시다.

 

https://www.acmicpc.net/problem/1620

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

문제가 너무 길어서 필요한 부분만 가져왔습니다.

 

간단히 요약하면 예제에서 주어지는 포켓몬 도감 리스트가 있습니다.

도감에는 1번 부터 N번까지 번호가 붙습니다.

포켓몬 이름을 물어보면 번호를 대답하고, 번호를 물어보면 포켓몬 이름을 대답하면 됩니다.

 

for문을 사용해서 풀려면 시간초과가 납니다.

그래서 질문 하나 당 O(1) 시간복잡도로 대답을 해야합니다.

 

1. JAVA

입력을 받을 때 포켓몬 이름, 번호를 키-밸류 쌍으로

그리고 포켓몬 번호, 이름을 키-밸류 쌍으로 저장합니다.

문제로 주어지는 입력값을 보고 두 곳에서 적절히 확인하고 답을 출력하면 됩니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Collections;
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));
        StringTokenizer st = new StringTokenizer(br.readLine());
	    
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
	    
        HashMap<String, Integer> a = new HashMap<String, Integer>();
        HashMap<Integer, String> a2 = new HashMap<Integer, String>();
	    
        for(int i = 1; i <= N; i++){
            String temp = br.readLine();
            a.put(temp, i);
            a2.put(i, temp);
        }
	    
        for(int i = 0; i < M; i++){
            String temp = br.readLine();
            if(a.containsKey(temp)) {
                System.out.println(a.get(temp));
            } else {
                System.out.println(a2.get(Integer.parseInt(temp)));
            }
        }
    }
}

 

2. C++

문자열을 정수타입으로 바꾸는 atoi 함수를 활용해서 문자열인지 정수인지 구분합니다.

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

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

	int N, M;
	string temp;
	map<string, int> a;
	map<int, string> a2;
	
	cin >> N >> M;
	for (int i = 1; i <= N; i++) {
		cin >> temp;
		a[temp] = i;
		a2[i] = temp;  
	}
	
	for (int i = 0; i < M; i++) {
		cin >> temp;
		if(atoi(temp.c_str()) == 0){
			cout << a[temp] << "\n";
		} else {
			cout << a2[atoi(temp.c_str())] << "\n";
		}
	}
	return 0;
}

 

 

3. 파이썬

파이썬은 문자인지 숫자인지 구분없이 그냥 모두 딕셔너리{}에 넣어버립니다.

그리고 그냥 찾으면 그만입니다. 

JAVA 또는 C++ 풀이에서도 String으로 모두 변환하여 파이썬과 같은 방법으로 찾아도 문제 없습니다.

import sys
input = sys.stdin.readline

N, M = map(int, input().split())

a = {}

for i in range(1, N+1):
    temp = input().rstrip()
    a[str(i)] = temp
    a[temp] = int(i)

for i in range(M):
    print(a[input().rstrip()])

특정조건하에 자료구조를 2개를 선언하는 스킬로 키 또는 값을 빠르게 찾는 방법을 알아보았습니다.