99클럽 코테 스터디 11일차 TIL C++ sort, unordered_map

오늘의 학습 키워드

문제1 : sort, unordered_map

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

공부한 내용 본인의 언어로 정리하기

문제1 : sort, unordered_map

 

(1) sort

sort 함수는 참가자와 완주자를 정렬한 후 두 벡터를 순차적으로 비교하여 처음으로 불일치하는 이름을 반환하거나, 참가자의 마지막 남은 이름을 반환하여 완주하지 못한 선수를 찾아내는 방식으로 문제를 해결합니다. sort를 사용하기 때문에 시간 복잡도는 O(N log N)입니다. 많은 데이터가 있을 때 다소 비효율적일 수 있습니다.

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

using namespace std;

string solution(vector<string> participant, vector<string> completion) {
    sort(participant.begin(), participant.end());
    sort(completion.begin(), completion.end());

    for (int i = 0; i < completion.size(); i++) {
        if (participant[i] != completion[i]) {
            return participant[i];
        }
    }
    return participant.back(); // 마지막 남은 이름 반환
}

• sort 사용법
  • 오름차순 정렬 : sort(벡터.begin(), 벡터.end())
  • 내림차순 정렬 : sort(벡터.begin(), 벡터.end(), greater<타입>())

(2) map을 활용한 풀이
map을 사용한 방법은 해시 맵을 통해 참가자의 이름을 카운트하고, 완주자의 이름을 제거하여 남은 이름을 찾는 방식입니다.

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

using namespace std;

string solution(vector<string> participant, vector<string> completion) {
    unordered_map<string, int> counts;

    // 모든 참가자의 이름을 해시 맵에 추가하여 횟수 카운트
    for (const string& name : participant) {
        counts[name]++;
    }

    // 완주자의 이름을 해시 맵에서 빼서 카운트 감소
    for (const string& name : completion) {
        counts[name]--;
    }

    // 카운트가 1인 이름이 완주하지 못한 참가자
    for (const auto& entry : counts) {
        if (entry.second > 0) {
            return entry.first;
        }
    }

    return ""; // 논리상 여기는 실행되지 않음
}

• const string& name을 사용하는 이유
  • 효율성과 불필요한 복사를 방지하기 위해서입니다. const string&는 문자열을 참조로 받아와 원본을 수정하지 않음을 의미하며, 복사를 방지해 성능을 향상시킵니다.

for (const string& name : participant) {
    // name은 participant의 각 요소를 참조로 받아와 불필요한 복사가 없습니다.
}

• unordered_map과 map
  • unordered_map: 평균 O(1)의 시간 복잡도로 빠른 탐색이 가능하지만, 내부 구조상 해시 충돌이 발생할 경우 최악의 경우 O(N)이 될 수 있습니다.
  • map: 이진 탐색 트리로 구현되어 항상 O(log N)의 탐색 성능을 보장합니다. 따라서 데이터 정렬이 필요한 경우 map을, 높은 속도를 요구할 경우 unordered_map을 사용하는 것이 좋습니다.

오늘의 회고

이번 학습을 통해 문제를 해결하는 다양한 방법을 비교할 수 있었습니다. sort는 직관적이지만 데이터가 많을 때 성능이 떨어지고, unordered_map을 이용하면 평균 O(N)의 빠른 성능으로 문제를 해결할 수 있다는 점에서 매우 효율적이었습니다. 또한, const string& 사용의 중요성과 map과 unordered_map의 특성을 이해하게 되었습니다.