[C++로 풀이] 순위 검색 (lower_bound, stringstream, 순열, 반복자 종류) ⭐⭐

📌 순위 검색

난이도 ⭐⭐

🚀 문제

🚀 내 풀이 ⭕

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

using namespace std;

vector<int> solution(vector<string> info, vector<string> query) {
    vector<int> answer;
    
    unordered_map<string, vector<int>> db;
    for (int i = 0; i < info.size(); ++i) {
        vector<string> applicant;
        string temp = "";
        for (int j = 0; j < info[i].length(); ++j) {
            if (info[i][j] == ' ') {
                applicant.push_back(temp);
                temp = "";
            }
            else
                temp += info[i][j];
        }
        applicant.push_back(temp);
        
        db[applicant[0] + applicant[1] + applicant[2] + applicant[3]].push_back(stoi(applicant[4]));

        for (int r = 1; r <= 4; ++r) {
            vector<bool> comb(4, false);
            for (int j = 0; j < r; ++j)
                comb[j] = true;
            do {
                string temp = "";
                for (int k = 0; k < 4; ++k) {
                    if (comb[k]) temp += '-';
                    else temp += applicant[k];
                }
                db[temp].push_back(stoi(applicant[4]));
            } while (prev_permutation(comb.begin(), comb.end()));
        }
    }
    
    for(auto& d : db)
        sort(d.second.begin(), d.second.end());

    for (int i = 0; i < query.size(); i++) {
        vector<string> condition;
        string temp = "";
        for (int j = 0; j < query[i].length(); ++j) {
            if (query[i][j] == ' ') {
                if (temp != "and")
                    condition.push_back(temp);
                temp = "";
            }
            else
                temp += query[i][j];
        }
        condition.push_back(temp);

        vector<int> score;
        score = db[condition[0] + condition[1] + condition[2] + condition[3]];
        vector<int>::iterator itr = lower_bound(score.begin(), score.end(), stoi(condition[4]));
        answer.push_back(score.end() - itr);
    }

    return answer;
}

🌈 생각해야 할 부분

이 문제는 ‘효율성’ 테스트가 있다. 그리고 info의 최대 크기는 50,000 이며 query의 최대 크기는 100,000 이라는 것을 염두해두어야 한다.

• 1️⃣ 미리 info 정보를 분류하여 캐싱해두어야한다.
  • query를 순회하면서 그 안에서 info 지원자 정보 하나하나가 조건에 들어맞는지를 검사한다면 O(n^2)으로 최대 50,000 * 100,000 = 5,000,000,000 무려 50억번의 연산을 해야할 수도 있다. 당연 시간초과다!
  • 다행히 수치라 그룹화 될 수 없는 “점수”는 제외하고. 언어는 4가지 (java/python/cpp/-), 직군은 4가지 (backend/frontend/-), 경력은 3가지 (junior/senior/-), 소울 푸드는 3가지 (pizza/chicken/-) 이렇게 나올 수 있는 조건의 조합이 최대 4 X 3 X 3 X 3 = 108 개 밖에 되지 않으므로 나올 수 있는 조합을 Key로 저장해두고, ‘점수’는 따로 해당 조합에 해당하는 지원자들의 점수 배열을 모아두어 이를 Value로 하는, 이런식의 분류를 미리 해놓는게 효율성을 높이는 코드가 될 것이다 조합의 후보가 최대 108개까지 될 수 있다는 말이고, 이미 있는 info 정보로 Key를 추가하면 108개 이하가 된다.
    • 점수는 어떤 조건이 나올지 알 수가 없으며 임의의 값 이상을 가지는 점수들을 찾으라는 것이 조건이 되기 때문에 조건은 조합별로 전부 모아서 저장해둘 필요가 있다. 점수를 제외한 조건들의 조합에서 임의의 값 이상을 가지는 점수들이 몇 개인지를 연산하면 된다! 예를 들어 [“-backend-pizza”] = [30, 50, 20] 를 설명하자면 “언어는 상관 없고, 직군은 backend 이며 경력은 상관 없고 소울 푸드는 pizza 인 지원자들은 점수가 각각 30, 50, 20점인 총 3명이 있다는 것이다. 이 3명의 점수들이 모여있는 배열이 이 "-backend-pizza" Key의 Value가 된다.
      • info[0] 지원자 한 명의 조건을 map에다가 분류하고 캐싱하는 작업을 완료하면 아래와 같이 4C0 + 4C1 + 4C2 + 4C3 + 4C4 = 16 가지 경우에 접근할 수 있게 된다. 마치 -이 4 개의 자리에 몇 개 뽑히느냐, 4개의 조건 중 몇 개의 어떤 조건들을 -로 할 것인가에 대한 조합의 수 합이라고 보면 된다. 즉, 매 지원자마다 아래와 같이 16가지로 -과 조건값을 조합한 것을 Key로 하여 점수를 Value에 추가하게 된다.
      • 모~~든 지원자들 분류 완료하면 ["- - - -"] Key의 Value는 모든 지원자들의 점수들이 다 들어있는 가장 큰 배열을 가지게 될 것이다.

        <info[0] 지원자 한명의 점수가 아래와 같은 16개의 Key에 추가될 수 있음>
        
        ✨- 가 0 개 뽑히는 경우✨ 4C0 개
        "javabackendjuniorpizza" Key에 150 추가
                
        ✨- 가 1 개 뽑히는 경우✨ 4C1 개
        "-backendjuniorpizza" Key에 150 추가
        "java-juniorpizza" Key에 150 추가
        "javabackend-pizza" Key에 150 추가
        "javabackendjunior-" Key에 150 추가
        
        ✨- 가 2 개 뽑히는 경우✨ 4C2 개
        "--juniorpizza" Key에 150 추가
        "-backend-pizza" Key에 150 추가
        "-backendjunior-" Key에 150 추가
        "java--pizza" Key에 150 추가
        "java-junior-" Key에 150 추가
        "javabackend--" Key에 150 추가
        
        ✨- 가 3 개 뽑히는 경우✨ 4C3 개
        "java---" Key에 150 추가
        "-backend--" Key에 150 추가
        "--junior-" Key에 150 추가
        "---pizza" Key에 150 추가
        
        ✨- 가 4 개 뽑히는 경우✨ 4C4 개
        "----" Key에 150 추가
        

• 2️⃣ query 조건에 해당하는 “점수의 하한선” (X점 이상을 찾는거니까 X점이거나 X점보다 큰 것중 가장 최소인 점수를 찾아야 함)을 찾을 땐 정렬 후 이진 탐색으로 찾자
  • 이진 탐색으로 찾아야 하는 이유는, "----" Key 의 경우 이 Key에 대응하는 점수 배열 Value 크기는 모든 지원자들의 점수가 들어가므로 최대 50,000 가 된다. 따라서 X점 이상을 찾을 때 “순차 탐색”하게 되면 O(n^2) 시간 초과가 날 수 있다. 매 쿼리 원소마다 순차 탐색을 해야하기 때문이다.
    • 최악의 경우를 생각해보면 query의 모든 원소가 “—-“ 고 찾는 점수가 점수 배열의 맨 끝에 있다면… 게다가 info와 uery가 최대 크기라면 또 50억번 연산을 해야하는 것이나 마찬가지이다. 이 경우엔 순차 탐색을 지양하고 이진 탐색으로 점수 하한선을 찾아 시간 복잡도를 최소화 해야한다.
      • 👉 이진 탐색로 점수 하한선을 찾는 것을 직접 구현할 수도 있지만 STL 알고리즘 헤더에서 이진 탐색 방식으로 해당 Key의 하한선을 찾아주는 lower_bound 함수를 지원하고 있다. 이를 사용하면 된다!
        • X점 이상을 찾을 때 일치하는 "X점"도 포함될 수 있으므로 upper_bound 가 아닌 lower_bound 를 사용해야 적절하다!

🌈 내 풀이 과정

1️⃣ info 미리 캐싱해두기

info 파싱

    for (int i = 0; i < info.size(); ++i) {
        vector<string> applicant;
        string temp = "";
        for (int j = 0; j < info[i].length(); ++j) {
            if (info[i][j] == ' ') {
                applicant.push_back(temp);
                temp = "";
            }
            else
                temp += info[i][j];
        }
        applicant.push_back(temp);

한 명의 지원자 문자열을 파싱하여 분류한다. (공백을 기준으로)

• 파싱이 끝난 후 applicant는 필연적으로 크기가 5가 된다.
  • ex) “java backend junior pizza 150” 👉 [“java”, “backend”, “junior”, “pizza”, “150”]
• 공백을 기준으로 applicant에 추가하도록 코드를 짰기 때문에 문자열의 마지막에 위치한 “점수”는 applicant에 추가되지 못한 채로 for문이 끝나게 되므로 for문 끝나고 한 번 더 applicant.push_back(temp);를 해주어야 한다.

map 등록 (‘-‘ 고려)

    unordered_map<string, vector<int>> db;
    for (int i = 0; i < info.size(); ++i) {
        //.. info 파싱

        db[applicant[0] + applicant[1] + applicant[2] + applicant[3]].push_back(stoi(applicant[4]));

        for (int r = 1; r <= 4; ++r) {
            vector<bool> comb(4, false);
            for (int j = 0; j < r; ++j)
                comb[j] = true;
            do {
                string temp = "";
                for (int k = 0; k < 4; ++k) {
                    if (comb[k]) temp += '-';
                    else temp += applicant[k];
                }
                db[temp].push_back(stoi(applicant[4]));
            } while (prev_permutation(comb.begin(), comb.end()));
        }
    }

• dp map
  • Key : 조건들의 문자열 조합 (최대 108가지의 Key가 나올 수 있음)
  • Value : 해당 조건들에 부합하는 지원자들의 점수 vector
• -를 0개 뽑은 경우. 4C0 = 1개.

    // ex) "pythonfrontendseniorchicken" Key에 210 추가
    db[applicant[0] + applicant[1] + applicant[2] + applicant[3]].push_back(stoi(applicant[4]));
  

• -를 r개 뽑은 경우 (r = 1,2,3,4) 4C1 + 4C2 + 4C3 + 4C4 = 15개
  • r = 2의 경우, 내림 차순 정렬 되어 있는 {true, true, false, false} 로 시작한 comb를 prev_permutation 을 사용하여 순열을 구해 나간다. true 위치에 대응하는 곳은 -로 하고, false 위치에 대응 하는 곳은 원래의 applicant 원소 문자열로 하여 키를 추가한다.
  • {true, true, false, true}인 상태(r = 3)라면 “–senior-“ Key에 210 이 추가될 것이다.

prev_permutation 에 대해서는 조합 포스트 참고

2️⃣ map 점수별로 정렬하기

    for(auto& d : db)
        sort(d.second.begin(), d.second.end());

Key 별로 저장되어 있는 점수들 중에서 이진 탐색으로 점수 하한선을 찾을 것이기 떄문에 점수들은 정렬이 미리 되어있어야 한다. 각 Key (first) 의 모든 점수 배열 Value (second)들을 정렬시킨다.

3️⃣ query 조건에 해당하는 점수들 중 X 점 이상 해당하는 것

query 파싱

    for (int i = 0; i < query.size(); i++) {
        vector<string> condition;
        string temp = "";
        for (int j = 0; j < query[i].length(); ++j) {
            if (query[i][j] == ' ') {
                if (temp != "and")
                    condition.push_back(temp);
                temp = "";
            }
            else
                temp += query[i][j];
        }
        condition.push_back(temp);

info 파싱했던 방식과 마찬가지로 query도 파싱하여 condition에 차례로 넣는다.(다 추가하고나면 크기는 5 가 될 것.) “and”는 무시하도록 한다.

Binary Search 로 점수 하한선 찾기 (lower_bound)

for (int i = 0; i < query.size(); i++) {
    // ... query 파싱

        vector<int> score;
        score = db[condition[0] + condition[1] + condition[2] + condition[3]];
        vector<int>::iterator itr = lower_bound(score.begin(), score.end(), stoi(condition[4]));
        answer.push_back(score.end() - itr); // score.size() - (score.begin() - itr) 와도 같다.

• 해당 조건들에 부합하는 Key 의 점수 배열을 score에 받는다.
  • [”- - -chicken”] Key 의 Value는 [50, 80, 150, 210]
• score에서 해당 X 점 (stoi(condition[4])) 이상인 점수의 반복자를 구한다.
  • lower_bound 함수
    • 세 번째 인수로 넘긴 Key와 1️⃣ Key 일치하는 것을 찾고 2️⃣ 일치하는 것이 없다면! Key 를 초과하는 것 中 가장 작은 것의 반복자를 리턴한다.
    • lower_bound(score.begin(), score.end(), 100) 은 150 원소의 반복자를 리턴하게 된다.
• 해당 조건 中 X 점 이상인 사람들의 수 = 해당 조건을 가진 사람들의 전체 명수 - X 점 이상의 하한선인 사람의 인덱스
  • ex) 100점 이상의 하한선은 150이며 이의 인덱스는 2 이다. (lower_bound는 반복자를 리턴하기 때문에 반복자끼리 뺄셈해주어 int 로 변환되게 해야 한다.)
    • [50, 80, 150, 210] 에서 100점 이상인 사람들은 4 - 2 = 2 명이 된다.
      • end() 반복자는 맨 끝 원소보다 한 칸 더 뒤인 없는 공간을 가리키는 반복자이기 때문에 정수로 생각해보면 그 컨테이너의 크기와도 같게 된다. 따라서 end() - itr 해주면 4 - 2 = 2 로 만들어주는 과정이나 마찬가지가 된다.

🚀 이 문제로 배운 것들 !!

이 문제 하나로 새롭게 알게 된게 많다.

🔥 정렬 연산은 반복문 밖에서 따로.

    for (int i = 0; i < query.size(); i++) {
        vector<string> condition;
        string temp = "";
        for (int j = 0; j < query[i].length(); ++j) {
            if (query[i][j] == ' ') {
                if (temp != "and")
                    condition.push_back(temp);
                temp = "";
            }
            else
                temp += query[i][j];
        }
        condition.push_back(temp);

        vector<int> score;
        score = db[condition[0] + condition[1] + condition[2] + condition[3]];
        
        sort(score.begin(), score.end()); // ✨✨✨ 주목 

        vector<int>::iterator itr = lower_bound(score.begin(), score.end(), stoi(condition[4]));
        answer.push_back(score.end() - itr);

원래는 저렇게 정렬을 query 순회 for문 안에서 lower_bound 로 탐색해주기 직전에 해줬었다. 이렇게 하니까 시간 초과가 발생하였다. 당연하게도 매 반복마다 정렬을 하는 것이니까 \(O(n^2logn)\) 과도 같아지기 때문이다! 그래서 반드시 query 순회 반복문 들어오기 전에 정렬을 따로 시켜줘야 한다. 왜 시간 초과가 나는지 모르겠어서 한참을 고민했는데 이것 때문이였다.. map 의 Value 를 정렬시키는 것이니까 이렇게 굳이 query 순회 for문 안에서 정렬해 줄 필요가 전혀 없다. 미리 query 순회 for문 들어가기 전에 해줘도 무방하다.

    for(auto& d : db)
        sort(d.second.begin(), d.second.end());

    for (int i = 0; i < query.size(); i++) {
        //...

이렇게 완전히 따로 ! ! !

🔥 반복자도 종류가 있다. (set은 반복자 사칙연산 불가능)

unordered_map<string, set<int>> db;

set 컨테이너는 자동으로 정렬이 된다는 것에 착안하여 처음에는 이렇게 Value를 vector가 아닌 set으로 했었다.

set<int>::iterator itr = lower_bound(score.begin(), score.end(), stoi(condition[4]));
answer.push_back(score.end() - itr); // ❌❌ 에러 발생! 

근데 set의 반복자끼리를 사칙연산 하려고 하니 자꾸 불가능하다고 에러가 뜨는 것이였다. vector 반복자는 잘만 되던데 뭐지 싶었다. (근데 set이 만약에 반복자 연산에 문제 없었다 하더라도 info for문 안에서 매번 자동 정렬이 된단 소리니까 set을 사용하면 시간초과가 될 수도 있었을 것 같다.)

반복자도 종류가 있다. 반복자끼리 + - 산술 연산이 가능한건 “임의 접근 반복자”를 가지는 vector, deque 밖에 없다.

STL 의 모든 컨테이너 혹은 함수들은 아래와 같은 종류의 반복자들을 지원하는데, 아래 반복자들 중 어느 것들까지 지원을 하느냐에 따라 사용할 수 있는 연산, 함수들이 달라진다.

반복자의 종류

1️⃣ 입력 반복자(Input)

• Read 및 접근 만 가능.
• Write 불가능
• 증감은 ++ 연산만 가능.
• 비교는 ==, != 연산만 가능.

cout << itr->size() << endl; // 접근 ⭕
뫄뫄 = *itr;  // 읽기 가능 ⭕ (간접 참조처럼 * 연산자)
itr++; // ++ 연산 가능 ⭕
if (itr1 == itr2); // ⭕
*itr = 뫄뫄;  // 쓰기 불가능 ❌ (간접 참조 수정 불가)

2️⃣ 출력 반복자(Output)

• Write 만 가능.
• Read 및 접근 불가능
• ++ 연산만 가능. (itr++)
• 비교 연산자 불가능

cout << itr->size() << endl; // 접근 불가능 ❌
뫄뫄 = *itr;  // 읽기 불가능 ❌
itr++; // ++ 연산 가능 ⭕
if (itr1 == itr2); // 비교 연산 불가능 ❌
*itr = 뫄뫄;  // 쓰기 가능 ⭕ 

3️⃣ 순방향 반복자(Forward)

• 읽기 쓰기 접근 다된다.
• 산술 연산 👉 ++만 가능
• 비교 연산 👉 ==, !=만 가능

4️⃣ 양방향 반복자(Bidirectional)

• 읽기 쓰기 접근 다된다.
• 산술 연산 👉 ++, -- 가능
• 비교 연산 👉 ==, !=만 가능

list, set, map 은 이 반복자를 지원한다. (그래서 set 의 반복자끼리 뺄셈을 하려 했을 때 불가능했던 것이다.)

이 양방향 반복자를 지원하지 않는 컨테이너는 알고리즘 헤더의 reverse() 함수를 사용할 수 없다. reverse 함수는 이 양방향 반복자를 사용하기 때문이다. 이처럼 함수, 연산에 따라 사용할 수 있는 반복자가 정해져있다는 것을 꼭 알아두자!

5️⃣ 임의접근 반복자(Random Access))

• 읽기 쓰기 접근 다된다.
• 산술 연산 👉 ++, --, ✨+, -, +=, -= 가능✨
• 비교 연산 👉 ==, !=, ✨>, <, >=, <= 가능✨
• 첨자 연산자 사용 가능 👉 []
  • itr[n]은 곧 *(itr + n)과도 같다.

    vector<int>::iterator itr;
    itr[4];  // itr 에서 4 칸 더 간 곳의 반복자! 
    

vector, deque 는 이 반복자를 지원한다. 그래서 반복자끼리 사칙연산을 해야한다면 vector를 사용해야 한다.

🔥 순회하며 파싱할 때 주의할 점

    for (int i = 0; i < info.size(); ++i) {
        vector<string> applicant;
        string temp = "";
        for (int j = 0; j < info[i].length(); ++j) {
            if (info[i][j] == ' ') {
                applicant.push_back(temp);
                temp = "";
            }
            else
                temp += info[i][j];
        }
        applicant.push_back(temp);

• 공백을 기준으로 applicant에 추가하도록 코드를 짰기 때문에 문자열의 마지막에 위치한 “점수”는 applicant에 추가되지 못한 채로 for문이 끝나게 되므로 for문 끝나고 한 번 더 applicant.push_back(temp);를 해주어야 한다.

이렇게 컨테이너를 순회하며 검사할 때 어떤 조건에 부합할 때만 특정 처리를 해준다면, 컨테이너의 마지막 부분은 처리 되야하는지 안되야하는지를 따져 이 마지막 부분도 꼭 처리를 해주어야 한다. 특히 위와 같은 식으로 파싱할 때!

🔥 stringstream 으로 파싱하기

        vector<string> applicant;
        string temp = "";
        for (int j = 0; j < info[i].length(); ++j) {
            if (info[i][j] == ' ') {
                applicant.push_back(temp);
                temp = "";
            }
            else
                temp += info[i][j];
        }
        applicant.push_back(temp);

이와 같은 긴 파싱 코드가

vector<string> applicant;
int score = 0;
istringstream iss(info[0]);
iss >> applicant[0] >> applicant[1] >> applicant[2] >> applicant[3] >> score;

이렇게 짧고 우아한 코드로 압축 될 수 있었다! 프로그래머스 다른 풀이의 좋아요를 가장 많이 받은 분의 코드를 보고 배울 수 있었다.

문자열도 cout, cin이 작동하는 방식처럼, 스트림 객체에 보관하고 이를 공백 기준으로 흘려보낼 수 있다.

• stringstream 타입의 문자열 스트림 객체
  • 스트림에 보관된 문자열을 공백을 기준으로 구분하여 파싱된 문자열을 >>, << 연산자에 흘려 보낸다.
  • istringstream은 오직 입력만, ostringstream은 오직 출력만 가능한 문자열 스트림 객체.
• 위 코드의 과정

  istringstream iss(info[0]); // iss 에 "java backend junior pizza 150" 가 들어간다.
  iss >> applicant[0]  // applicant[0] = "java", iss에는 "backend junior pizza 150"이 남아있다.
  >> applicant[1] // applicant[1] = "backend", iss에는 "junior pizza 150"이 남아있다.
  >> applicant[2] // applicant[2] = "junior", iss에는 "pizza 150"이 남아있다.
  >> applicant[3] // applicant[3] = "pizza", iss에는 "150"이 남아있다.
  >> score // score = 150, ⭐이렇게 int 에도 잘만 변환되서 들어간다.⭐ iss에는 남아있는 문자열이 업삳.
  

참고 🖱 18.3 문자열 스트림

나 포스팅 한적 있었네.. 왜 초면인 것 같냐..

🔥 비트마스크로 조합 구하기 (nC0 + nC1 + .. + nCn 을 구하는 경우에만 해당)

        db[applicant[0] + applicant[1] + applicant[2] + applicant[3]].push_back(stoi(applicant[4]));
        for (int r = 1; r <= 4; ++r) {
            vector<bool> comb(4, false);
            for (int j = 0; j < r; ++j)
                comb[j] = true;
            do {
                string temp = "";
                for (int k = 0; k < 4; ++k) {
                    if (comb[k]) temp += '-';
                    else temp += applicant[k];
                }
                db[temp].push_back(stoi(applicant[4]));
            } while (prev_permutation(comb.begin(), comb.end()));
        }

위 코드가

for (int i = 0; i < info.size(); ++i){
    //...
    string str = "";
    for(int mask = 0; mask < 16; mask++){
        for (int k = 0; k < 4; k++){
            str += (mask & (1 << k)) ? '-' : applicant[k];
            db[str].push_back(score);
        }
    }

이렇게 짧고 우아한 코드로 압축 될 수 있었다! 이 역시 프로그래머스 다른 풀이의 좋아요를 가장 많이 받은 분의 코드를 보고 배울 수 있었다.

4 자리에서 - 이 들어갈 수 있는 경우는 4C0 + 4C1 + 4C2 + 4C3 + 4C4 = 16 가지가 된다. 이는 사실

0000 
👉 0 
👉 {F,F,F,F} 로 만들 수 있는 모든 순열과도 같음

1000 0100 0010 0001
👉 1 2 4 8
👉 {T,F,F,F} 로 만들 수 있는 모든 순열과도 같음

1100 1010 1001 0110 0101 0011 
👉 12 10 9 6 5 3
👉 {T,T,F,F} 로 만들 수 있는 모든 순열과도 같음

1110 1101 1011 0111
👉 14 13 11 7
👉 {T,T,T,F} 로 만들 수 있는 모든 순열과도 같음

1111
👉 15
👉 {T,T,T,T} 로 만들 수 있는 모든 순열과도 같음

이 0000 ~ 1111 즉, 0 ~ 15 인 16 가지의 4 자리 비트는는 -가 들어갈 수 있는 모든 케이스들이 되는 것이나 마찬가지이다.

• 예를 들어 위 코드에서 현재 mask가 13 일 땐
  • (mask & (1 « k)
    • 1101 & 0001 👉 True 이므로 - 추가 👉 str = “-“
    • 1101 & 0010 👉 False 이므로 applicant[1] 추가 👉 str = “-backend”
    • 1101 & 0100 👉 True 이므로 - 추가 👉 str = “-backend-“
    • 1101 & 1000 👉 True 이므로 - 추가 👉 str = “-backend–”
      • 1 자리에 -가 들어가는 식은 아니지만 16가지 비트들은 서로 다 데칼코마니처럼 대응이되므로 이렇게 해도 될듯 하다. (최하위 비트인 오른쪽부터 덧붙여나가니까 마치 1011 자리에 -을 붙이는 것과도 같아진다.)

🔥 map 의 value 자동 생성

        if (db.find(applicant[0] + applicant[1] + applicant[2] + applicant[3]) == db.end()) {
            vector<int> score;
            db[applicant[0] + applicant[1] + applicant[2] + applicant[3]] = score;
        }
        db[applicant[0] + applicant[1] + applicant[2] + applicant[3]].push_back(stoi(applicant[4]));

            do {
                string temp = "";
                for (int k = 0; k < 4; ++k) {
                    if (comb[k]) temp += '-';
                    else temp += applicant[k];
                }
                if (db.find(temp) == db.end()) {
                    vector<int> score;
                    db[temp] = score;
                }
                db[temp].push_back(stoi(applicant[4]));
            } while (prev_permutation(comb.begin(), comb.end()));

처음엔 위와같이 Key 가 없다면 vector를 손수 생성하여 Value로 추가해주었다. 근데 굳이 이렇게 안해도 됐었다.. map은 Value를 자동으로 생성해주는 것 같다.

db[applicant[0] + applicant[1] + applicant[2] + applicant[3]].push_back(stoi(applicant[4]));
//...
db[temp].push_back(stoi(applicant[4]));

벡터를 직접 생성해서 추가해줄 필요 없이 위와같이 해도 문제없이 잘 돌아갔다. map 이 빈 vector를 자동으로 만들어준 후 추가 시키나보다.

---

🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우 
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄

맨 위로 이동하기

Programmers 카테고리 내 다른 글 보러가기