[HackerRank](c++) Sales by Match

https://www.hackerrank.com/challenges/sock-merchant/problem?h_l=interview&playlist_slugs%5B%5D=interview-preparation-kit&playlist_slugs%5B%5D=warmup 

Sales by Match | HackerRank

 

 

 

문제 : 양말의 쌍 개수 구하기

 

- 배열안에는 양말별로 색이 지정되어있다.

 

- 색깔은 0부터 100까지로 구별되어있다.

 

- 한쌍은 두개의 양말로 이루워져있으면 한쌍에는 같은색의 양말이어야 한다.,

 

- 해당배열에 존재하는 총 양말의 쌍을 구하여라.

 

 

 

 

풀이법 1 (HashMap 방식)

 

- 해당 양말의 색을 key로 설정하여 map에 넣는다.

 

- for문을 돌려 ar에 저장되어있는 모든 양말의 색을 구별하여 map 존재할경우 개수를 추가, 존재하지않을경우 새로 생성한다.

 

- for문을 돌려 map에 저장된 개수를 2로 나누어서 그값을 answer에 추가한다.

 

- answer를 반환한다.

 

int sockMerchant(int n, vector<int> ar) {
    map<int, int> map;
    for (size_t i = 0; i < ar.size(); i++)
    {
        if (map.find(ar[i]) != map.end())
        {
            map[ar[i]]++;
        }
        else {
            map.insert(make_pair(ar[i], 1));
        }
    }

    int answer = 0;

    for (auto iter : map)
    {
        answer += iter.second / 2;
    }
    return answer;
}

 

풀이법2 (Memoization 방식)

 

- 해당 양말의 색깔이 101가지이므로 int 배열을 101까지 생성한다

 

- for문을 돌려 ar의 색깔에 맞는 인덱스에 1를 추가한다

 

- for문을 돌려 temp의 개수나누기 2를 한후 answer에 더한다.

 

- answer를 반환한다. 

int sockMerchant1(int n, vector<int> ar) {
    int temp[101] = {};
    for (size_t i = 0; i < ar.size(); i++)
    {
        temp[ar[i]]++;
    }

    int answer = 0;

    for (auto iter : temp)
    {
        answer += iter / 2;
    }
    return answer;
}

 

https://github.com/Natejin/CodeTest/blob/master/HackerRank/HackerRank/Sales%20by%20Match.cpp