Hash Map

 

Hash Map

C++ 에서는 unordered_map 컨테이너로 제공되는 것으로 알고 있다.

 

나름 map, unordered_map 을 이용해서 문제를 잘 푼다고 생각했는데

코드트리에서 실력을 진단하던 중 다음 문제에 가로막혀 버렸다.

 

두 수의 합

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

 

중복 가능한 수의 집합에서 두 개의 수를 조합했을 때

특정 수를 만들 수 있는 조합의 수를 구하는 문제이다.

 

문제를 보자마자 map을 통해서 숫자의 수를 세고

차이 값을 기준으로 답을 구하면 될 거라고 생각했다.

 

#include <iostream>
#include <map>

using namespace std;

int n, k;
int ans = 0;
int arr[100001];
map<int, int> m;

int main()
{
    cin >> n >> k;

    for(int i=0;i<n;i++)
    {
    	int num;
        cin >> num;
        
        m[num]++;
    }
    
    for(auto item : m)
   	{
    	// 현재 수와 조합해서 k 를 만들 숫자가 있는가 ?
    	if (m.count(k - item.fisrt) != 0)
        {
        	// 만약 현재 수 * 2 = k 라면
        	if (k - item.first == item.first)
            {
            	ans++;
                m[item.first] -= 2;
            }
            // 그 외의 경우
            else
            {
            	ans++;
                m[item.first] -= 1;
                m[k - item.first] -= 1;
            }
        }
    }

    cout << ans;

    return 0;
}

 

완벽하다고 생각했는데 문제가 발생했다.

 

우선 count 의 경우 map 컨테이너에 내가 찾고자 하는 값이 있는지 없는지 판별해준다.

 

즉, 내가 이미 다 사용해서 k 의 키 값에 0 val 이 들어가 있더라도

count는 있다고 판별할 것이다.

m.count(k) = 1 -> 있다

m.count(k) = 0 -> 없다

 

이게 내가 착각했던 가장 큰 문제였다.

 

그래서 이번엔 val 값을 기준으로 답을 찾고자 했다.

 

int main()
{
    for(auto item : m)
   	{
    	// 현재 수와 조합해서 k 를 만들 숫자가 있는가 ?
    	if (m[k - item.first] != 0)
        {
        	// 만약 현재 수 * 2 = k 라면
        	if (k - item.first == item.first)
            {
            	ans += m[item.first] / 2;
                m[item.first] %= 2;
            }
            // 그 외의 경우
            else
            {
                int mini = min(m[item.first], m[k-item.first]);
            	ans += mini;
                m[item.first] -= mini;
                m[k - item.first] -= mini;
            }
        }
    }

    cout << ans;

    return 0;
}

 

한번 살펴본 item 의 경우 다시 돌아와서 판별할 수 없기 때문에

한번에 처리해주고자 하였다.

 

하지만, 이번에도 틀렸다.

코드트리는 참 친절하게도 어떤 테케에서 틀렸는지 알려준다.

 

 

이 문제는 서로 다른 자리 위치에 있는 두 수를 뽑아 합쳤을 때 k 가 되는지 판별해야 하는 문제다.

그러므로 (0, 1), (0, 2), (0, 3), (0, 4), (1, 2), (1, 3) ... 무수히 많은 결과가 나오지만

내가 짠 코드는 단 2개의 케이스만 발견할 뿐이었다.

 

10만개의 숫자에 대해서 직접 조합을 모두 구해보는 것은

10만 x 10만으로 시간복잡도 상 불가능한 방법이었고 1시간 반정도 생각했지만

더이상 방법을 생각해낼 수가 없어서 문제의 해설을 보게 되었다.

 

#include <iostream>
#include <unordered_map>

using namespace std;

int n, k;
int ans = 0;
int arr[100001];
unordered_map<int, int> m;

int main()
{
    cin >> n >> k;

    for(int i=0;i<n;i++) cin >> arr[i];

    for(int i=0;i<n;i++)
    {
        // k = arr[i] + x 이므로 x 가 있는지 체크하고 더해 줌
        ans += m[k-arr[i]];
		
        // k = arr[i] + x 는 k = arr[i] + arr[j] 와 같으므로 j 일 때 i 가 있음을 알려주어야 함
        m[arr[i]]++;
    }

    cout << ans;

    return 0;
}

 

나는 처음부터 map 에 넣어서 풀려고 생각했는데

다시 생각해보니 중복된 원소가 서로 다른 위치에 주어질 수 있기 때문에

무작정 map을 사용한 판단 자체가 틀렸던 것이다.

 

하다못해 unordered_map 을 사용했으면 더 나았을까 ?

 

위 풀이는 원소의 순서는 배열로 관리해주고

k 에 도달하기 위한 조합 값을 map 으로 관리하는 방법인데

 

정말 생각지도 못했다.

아직도 멀었다 ...