map, unordered_map

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

프로그래머스

본 메모는 프로그래머스 '성격 유형 검사' 문제 풀이 이후 정리함

 

• 성격 유형 검사

문제:

나만의 카카오 성격 유형 검사지를 만들려고 합니다.
성격 유형 검사는 다음과 같은 4개 지표로 성격 유형을 구분합니다. 성격은 각 지표에서 두 유형 중 하나로 결정됩니다.

지표 번호	성격 유형
1번 지표	라이언형(R), 튜브형(T)
2번 지표	콘형(C), 프로도형(F)
3번 지표	제이지형(J), 무지형(M)
4번 지표	어피치형(A), 네오형(N)

4개의 지표가 있으므로 성격 유형은 총 16(=2 x 2 x 2 x 2)가지가 나올 수 있습니다. 예를 들어, "RFMN"이나 "TCMA"와 같은 성격 유형이 있습니다.

검사지에는 총 n개의 질문이 있고, 각 질문에는 아래와 같은 7개의 선택지가 있습니다.
(매우 비동의, 비동의, 약간 비동의, 모르겠음, 약간 동의, 동의, 매우 동의)
각 질문은 1가지 지표로 성격 유형 점수를 판단합니다.
예를 들어, 어떤 한 질문에서 4번 지표로 아래 표처럼 점수를 매길 수 있습니다.
선택지성격 유형 점수매우 비동의네오형 3점비동의네오형 2점약간 비동의네오형 1점모르겠음어떤 성격 유형도 점수를 얻지 않습니다약간 동의어피치형 1점동의어피치형 2점매우 동의어피치형 3점
이때 검사자가 질문에서 약간 동의 선택지를 선택할 경우 어피치형(A) 성격 유형 1점을 받게 됩니다. 만약 검사자가 매우 비동의 선택지를 선택할 경우 네오형(N) 성격 유형 3점을 받게 됩니다.
위 예시처럼 네오형이 비동의, 어피치형이 동의인 경우만 주어지지 않고, 질문에 따라 네오형이 동의, 어피치형이 비동의인 경우도 주어질 수 있습니다.
하지만 각 선택지는 고정적인 크기의 점수를 가지고 있습니다.
매우 동의나 매우 비동의 선택지를 선택하면 3점을 얻습니다.
동의나 비동의 선택지를 선택하면 2점을 얻습니다.
약간 동의나 약간 비동의 선택지를 선택하면 1점을 얻습니다.
모르겠음 선택지를 선택하면 점수를 얻지 않습니다.
검사 결과는 모든 질문의 성격 유형 점수를 더하여 각 지표에서 더 높은 점수를 받은 성격 유형이 검사자의 성격 유형이라고 판단합니다. 단, 하나의 지표에서 각 성격 유형 점수가 같으면, 두 성격 유형 중 사전 순으로 빠른 성격 유형을 검사자의 성격 유형이라고 판단합니다.
질문마다 판단하는 지표를 담은 1차원 문자열 배열 survey와 검사자가 각 질문마다 선택한 선택지를 담은 1차원 정수 배열 choices가 매개변수로 주어집니다. 이때, 검사자의 성격 유형 검사 결과를 지표 번호 순서대로 return 하도록 solution 함수를 완성해주세요.

 

제한 사항

• 1 ≤ survey의 길이 ( = n) ≤ 1,000
• survey의 원소는 "RT", "TR", "FC", "CF", "MJ", "JM", "AN", "NA" 중 하나입니다.
• survey[i]의 첫 번째 캐릭터는 i+1번 질문의 비동의 관련 선택지를 선택하면 받는 성격 유형을 의미합니다.
• survey[i]의 두 번째 캐릭터는 i+1번 질문의 동의 관련 선택지를 선택하면 받는 성격 유형을 의미합니다.
• choices의 길이 = survey의 길이
• choices[i]는 검사자가 선택한 i+1번째 질문의 선택지를 의미합니다.
• 1 ≤ choices의 원소 ≤ 7

---

#include <string>
#include <vector>
#include <unordered_map>

using namespace std;

string solution(vector<string> survey, vector<int> choices) 
{
    unordered_map<char, int> score;  // 성격 유형 점수 저장
    
    // 성격 유형 쌍 정의
    vector<pair<char, char>> types = { {'R', 'T'}, {'C', 'F'}, {'J', 'M'}, {'A', 'N'} };
    
    // 점수 계산
    for (size_t i = 0; i < survey.size(); i++) 
    {
        char disagree = survey[i][0]; // 비동의 측 (앞쪽 문자)
        char agree = survey[i][1];    // 동의 측 (뒷쪽 문자)
        int choice = choices[i];

        if (choice < 4) 
        {  // 비동의 선택
            score[disagree] += 4 - choice;
        } 
        
        else if (choice > 4) 
        {  // 동의 선택
            score[agree] += choice - 4;
        }
    }
    
    // 최종 성격 유형 결정
    string result = "";
    for (auto& type : types) 
    {
        char first = type.first, second = type.second;
        result += (score[first] >= score[second]) ? first : second;
    }
    return result;
}

• map, unordered_map

위 코드에서 일반 map이 아닌 unordered_map이 사용된 이유는 빠른 검색 속도 때문이다.

map은 자동으로 오름차순 정렬이 필요한 정렬된 데이터를 유지할 때, 혹은 순차적으로 데이터를 탐색해야 하는 경우 순서대로 순회하기 위해서 사용한다. 그에 비해 unordered_map은 내부적인 해시 테이블을 사용해서 데이터를 검색, 삽입, 삭제하는데 특화 되어있고, 알파벳 순서에 연연하지 않아 위 코드에 적합하다.

 

둘 다 C++ STL에서 제공하는 연관 컨테이너로 키 - 값의 쌍으로 이루어진 형태로 데이터를 저장하는 자료 구조이다.

• map

map은 균형 이진 탐색 트리 (Red-Black Tree) 기반이다.

정렬된 상태로 저장하며 중복 키를 사용 불가하다는 특징이 있으며 반복자를 사용해 순회하면 키의 오름차순으로 순회가 가능하다.

 

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

int main()
{
    map<int, string> student;

    // 삽입
    student[101] = "Alice";
    student[102] = "Bob";
    student[103] = "Charlie";

    // 탐색
    cout << "ID 102: " << student[102] << endl;
	// 출력 : ID 102: Bob
    
    // 순차 출력 (자동 오름차순 정렬)
    for (auto& s : student) 
    {
        cout << s.first << ": " << s.second << endl;
    }
    //출력: 101: Alice
    //      102: Bob
    //      103: Charlie

    return 0;
}

 map은 키 값이 정렬된 순서로 필요할 때, 삽입, 삭제, 탐색이 모두 중요할 때, 최악의 경우에도 안정적인 성능이 필요할 때 사용된다

 

---

• unordered_map

unordered_map은 데이터의 순서가 정렬되지 않고 중복 키를 사용하는 것이 불가능하며 해시 테이블 특성상 map보다 메모리를 더욱 많이 사용한다.

 

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

int main()
{
    map<int, string> student;

    // 삽입
    student[101] = "Alice";
    student[102] = "Bob";
    student[103] = "Charlie";

    // 탐색
    cout << "ID 102: " << student[102] << endl;
	// 출력 : ID 102: Bob
    
    // 순차 출력 (자동 오름차순 정렬)
    for (auto& s : student) 
    {
        cout << s.first << ": " << s.second << endl;
    }
    //출력 순서가 다를 수 있음
    //출력: 103: Charlie
    //      102: Bob
    //      101: Alice

    return 0;
}

map과 같은 코드를 사용하지만 순차 출력시 순서가 다를 수 있다.

unordered_map은 데이터의 정렬이 필요하지 않거나 탐색속도가 중요할 때 사용된다.

결과적으로 정렬이 필요할 때는 map을, 속도가 중요하고 정렬이 필요 없다면 unordered_map을 사용하는 것이 좋다.