[프로그래머스 고득점 kit] 해시 (map) 문제 정리 (c++)

이번엔 해시, 혹은 c++ 헤더에 정의되어있는 "map" 자료구조를 통해 해결할 수 있는 문제들에 대하여 이야기해보겠다.

 

map은 기본적으로 {key,value} 의 데이터쌍을 가진다. 

사용하기 위해선 

#include<map>
using namespace std;

위 헤더파일을 include해야한다.

 

정의는 

map<key의 데이터 타입, value의 데이터 타입> 으로 이루어지며, string형  key 값을 가지고, int형 value 값을 가지는 map의 경우

map<string,int> ma;

와 같이 정의하면 된다.

 

 

https://school.programmers.co.kr/learn/courses/30/parts/12077

프로그래머스

map이 어디서 사용되고, 왜 사용되는가? 에 대한 이야기는 위 링크에 정리된 해시에 관한 문제들을 같이 해결하며

알아보자!

 

 

 

1) 완주하지 못한 선수

 

https://school.programmers.co.kr/learn/courses/30/lessons/42576

프로그래머스

#include <string>
#include <vector>
#include<map>
#include<iostream>
using namespace std;

//map 사용


map<string, int> ma;
string solution(vector<string> participant, vector<string> completion) {
    string answer = "";
    for (int i = 0; i < completion.size(); i++) ma[completion[i]]++;

    for (int i = 0; i < participant.size(); i++) ma[participant[i]]--;

    for (auto it : ma) {   //  it.first= key   it.second=value
        if (it.second < 0) answer = it.first;
    }

    return answer;
}

기본적인 map 문제. 

이 문제가 map을 사용하는 이유를 잘 설명해준다.

map은 {key,value} 의 데이터를 저장하는데, 여기서 key는 결국 "종류" 를 나타내고,

이는 곧  종류별로 어떠한 값을 산출하는 것에 최적화 되어있는 자료구조임을 의미한다.

(데이터 베이스에서 SQL을 사용해본 사람이라면 group by와 같은 그룹 함수에 대해 생각해보자. )

 

이 문제는 결국 요약하자면, 참여자 목록에는 있지만, 완주자 목록에는 없는 사람을 찾는 문제이다.

map의 {key, value}에  {사람이름, 해당 이름을 가진 완주자 수 -해당이름을 가진 참여자 수 } 를 집계한다면

완주하지 못한 사람은 1명뿐이므로, value값이 -1 인 key값이 완주하지 못한 사람의 이름이다.

 

 

 

 

2) 폰켓몬

 

https://school.programmers.co.kr/learn/courses/30/lessons/1845

프로그래머스

#include <vector>
#include <map>

using namespace std;

int solution(vector<int> nums)
{
    map<int, int> hash;

    for (auto num : nums) {
        hash[num] += 1;
    }  
    return min(hash.size(), nums.size() / 2);  //map의 size: key, value 순서쌍의 개수 >>
}

map의 특성을 활용한 문제.

 

vector는 가짓수를 알아내는 문제와는 어울리지 않는 자료구조이다.

 

arr는 크기를 미리 정의해주어야 하기에, arr 안에서 실제 삽입된 값의 개수를 알 수 없다.

int arr[100] ;

-> arr.size()==100;

 

하지만 map의 경우,  {key,value} 쌍으로 구성된 red-black tree 구조이고, 실제 삽입한 키의 개수만큼 size가 책정된다.

hash.size() == hash에 실제 들어있는 {key,value} 순서쌍 개수.

 

 

* 부가 정보

 

map<int,int> m; 
m[0];

 

이렇게 정의된 map에서, 존재하지 않는 key 값에 접근하면 어떻게 될까?

m[0] ->  key값이 0인 value 값을 리턴해야하지만, map형 자료구조 "m"에는 아직 어떠한 {key,value} 데이터도 들어오지 않았다.

이 경우, 해당 {key ,value의 디폴트값 ( int -> 0 ) } 이런 형식으로 값을 insert하게 된다.

따라서 위의 문제에서

hash[num]+=1;

이 라인의 의미는 다음과 같다.

"만약 num을 key값으로 가지는 데이터가 없다면, {num,0} 을 삽입하고, 존재한다면 기존 value값에 1을 더한다."

 

따라서 위 1줄의 라인만으로 어떠한 key의 value값이 해당 key의 개수로 정의될 수 있는 것이다.

 

 

 

3) 전화번호 목록

 

https://school.programmers.co.kr/learn/courses/30/lessons/42577

프로그래머스

#include <string>
#include <vector>
#include<map>
#include<iostream>
using namespace std;

map<string, bool> ma;
bool solution(vector<string> phone_book) {
    bool answer = true;
    for (int i = 0; i < phone_book.size(); i++) ma[phone_book[i]] = true;

    for (int i = 0; i < phone_book.size(); i++) {
        string str = "";
        //해당 번호가 다른 번호를 접두어로 가지는지 check. 동일한 번호는x이기에 size-1까지만.
        for (int len = 0; len < phone_book[i].size() - 1; len++) {
            str += phone_book[i][len];
            if (ma[str]) answer = false;   //ma[str] 에서 key값 str이 존재하지 않으면, 0( value 디폴트) 값을 삽입.
        }
    }
    return answer;
}

결국 무식한 방법으로 해결하였다.

우선 phone_book vector 전체를 돌며 

{ "전화번호",ture } 의 데이터쌍을 map에 저장했다.

이후 다시 한번 phone_book을 탐색하며, 해당 번호가 접두어로써 가질 수 있는 숫자가 첫 반복문에서 insert되었는지 확인한다.

 

두번째 반복문 예시:

"12345"  ->   "1" 이 존재?   "12" 존재?   "123" 존재?  "1234" 존재?

이렇게 길이-1까지 체크한다.

 

여기서 "12345"는 체크하지 않는 이유는 동일한 전화번호가 없다는 전제하에 자기자신을 배제하기 위함이다.

(만약 길이 끝까지 탐색했다면, 본인이 본인의 접두어로 사용되는 경우도 검출되었을 것이다.)

 

 

 

4) 위장

 

https://school.programmers.co.kr/learn/courses/30/lessons/42578

프로그래머스

 

#include <string>
#include <vector>
#include<map>
using namespace std;
map<string, int> ma;
int solution(vector<vector<string>> clothes) {
    int answer = 1;
    for (auto cloth : clothes) {
        string name = cloth[0], kind = cloth[1];
        ma[kind]++;
    }

    for (auto m : ma) {
        answer *= (m.second + 1); //옷 종류별 가짓수 +1 (안입기)
    }
    answer--;//아무것도 안입는 경우는 제외한다.

    return answer;
}

이제 슬슬 map에 대해서 감이 올 것이다. 결국 "가짓수", "종류별" 에 대한 문제는 map으로 해결하면 된다.

clothes 벡터에 들어온 input들을 옷의 종류별로 구분하고, 모든 옷 종류에 대한 경우의 수를 찾으면 된다.

 

ex:   

모자: 3개

상의: 2개

 

-> (3+1) * (2+1) -1

 

각 옷의 종류별로 아무것도 입지 않는 경우의 수를 생각해 +1 을 하고, 아무것도 입지 않는 경우를 제외하기위해 -1을 해준다.

 

 

 

5) 베스트 앨범

 

https://school.programmers.co.kr/learn/courses/30/lessons/42579

프로그래머스

 

#include <string>
#include <vector>
#include<map>
#include<algorithm>
using namespace std;

bool compare(const pair<int, pair<int, int> >& a, const pair<int, pair<int, int> >& b) {
    return a.first > b.first;
}

map<string, pair<int, pair<int, int> > > ma;// {총 재생량, {Max_idx,secondMax_idx} }
vector<int> solution(vector<string> genres, vector<int> plays) {
    vector<int> answer;
    int max = -1, sec_max = -1;
    plays.push_back(-1);
    int init = plays.size() - 1;
    for (int i = 0; i < genres.size(); i++) {
        if (ma.count(genres[i]) == 0)
            ma[genres[i]] = { 0,{init,init} };
        ma[genres[i]].first += plays[i];

        if (plays[ma[genres[i]].second.first] < plays[i]) {
            ma[genres[i]].second.second = ma[genres[i]].second.first;
            ma[genres[i]].second.first = i;
        }
        else if (plays[ma[genres[i]].second.second] < plays[i])
            ma[genres[i]].second.second = i;
    }

    //총 재생량이 높은 장르가 먼저 -> 총 재생량으로 sort가 필요하다.
    //map은 기본적으로 key의 오름차순으로 정렬되있는 구조.
    //map을 value 값 기준 sort 불가능하다!! -> vector로 옮겨서 sort
    vector< pair<int, pair<int, int>> > v;
    for (auto m : ma) {
        v.push_back(m.second);
    }

    sort(v.begin(), v.end(), compare);//총 재생량의 내림차순 정렬.

    for (auto vec : v) {
        pair<int, pair<int, int> > val = vec;
        if (val.second.first != init) //max가 디폴트값( 갱신 x) 아니라면
            answer.push_back(val.second.first);
        if (val.second.second != init)//second max가 디폴트값 아니라면
            answer.push_back(val.second.second);
    }
    return answer;
}

각 장르별로 {총 재생 수, {가장 높은 재생수를 기록한 음악의 index값, 두번째로 높은 재생수를 기록한 음악의 index값} }

를 저장하면 풀 수 있는 문제이다.

map자료구조를 통해 "장르별" 이라는 그룹화를 만들어준 뒤 위의 데이터 값을 갱신해주면 된다.

 

하지만, 이 문제에서는 추가로 1가지가 더 요구된다.

"총 재생 수 가 높은 장르가 앨범의 앞에 위치한다"

 

즉 "총 재생수" 라는 map의 value값에 대한 정렬이 필요한데, map은 value값을 기준으로 정렬이 불가하다.

(map은 key값 기준 오름차순으로 자동 정렬되는 구조를 가진다)

 

따라서 map의 pair<int,pair<int,int>> 값들( 장르별 필요한 정보들) 을 vector에 옮겨서 sort해야한다.

 

*부가 정보

 

map은 기본적으로 key값을 기준으로 sort되는 tree 구조를 가지지만, 이것이 상관 없을 경우,

c++ 헤더의 unordered_map 을 사용해서 key값을 기준으로 정렬하지 않는 unordered_map을 사용 가능하다.