[Algorithm] 해커랭크 - Hash Tables: Ice Cream Parlor

https://www.hackerrank.com/challenges/ctci-ice-cream-parlor/problem

 N개의 아이스크림들 중 서로 다른 2개를 골라야 하는데, 주어진 Money와 두 아이스크림 가격의 합이 같은 경우를 찾는 것이다. 

 아이스크림은 정수의 나열로 주어지며 아이스크림의 ID는 그 수의 순서, 아이스크림의 가격은 그 수가 된다.

(단 1번째 아이스크림부터 순차적으로 검사)

문제 설명이 애매한것인지, 내가 영어를 못해서인지 모르겠는데 문제 이해만 하는데 너무 오래 걸렸다.

단순한 두 수의합 문제이므로 순차적으로 검사하되 첫번째 아이스크림을 고른 다음에 해시 테이블을 이용해 (Money - 첫 아이스크림 가격)과 같은 가격의 아이스크림 ID(순서)를 찾으면 된다.

즉 Key = 아이스크림 가격 Value = 아이스크림 ID인 해시 테이블을 생성해서 활용하면 된다.

void solve(vector <int> arr, int money) {
    map<int, vector<int>* > maps; //cost and vector what includes ids
    for(int i = 0; i < arr.size(); i++)
    {
        maps[arr[i]] = new vector<int>();
        maps[arr[i]]->push_back(i);
    }
    for(int i = 0; i < arr.size(); i++)
    {
        int nowMoney = money - arr[i];
        if(maps.find(nowMoney) != maps.end())
        {
            cout << i + 1 << " " << maps[nowMoney]->at(0) + 1 << endl;
            return;
        }
    }
}

풀이시간 : 2시간

문제점 :

1. 영어 문해력이 부족해 문제 이해를 잘못해 조건을 제대로 숙지하지 못함

2. 해시테이블로 쓸 수 있는 자료구조들에 대한 응용력이 부족했음