프로그래머스 완주하지 못한 선수

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

프로그래머스

생각보다 간단한 문제이지만, 해시가 주제 이므로 해시 map을 이용해서 풀었다.

내가 생각한 알고리즘은 다음과 같다.

1. 먼저 unordered_map을 이용하여 참가자 목록을 관리하기 위해 list를 선언해준다.
2. 참가자 목록을 추가하고, 기존에 같은 이름이 있는지 확인 후, 있다면 값을 증가시킨다.
3. 완주한 사람을 찾아서 해당 이름의 value값을 감소 시켜 준다.
4. 감소시켜 0이 되면 list에서 제외 시킨다.
5. 마지막으로 list에 남는 이름이 완주를 못한 사람이고 answer에 이름을 넣어준다.

해시맵을 이용한 코드

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

using namespace std;

string solution(vector<string> participant, vector<string> completion) {
    string answer = "";
    
    unordered_map<string, int> list;
    
    for (const string& name : participant) {
        list[name]++;
    }
    
    for (const string& name : completion) {
        
            list[name]--;
            
            if (list[name] == 0) {
                list.erase(name);
            }
        }
    }
    

    answer = list.begin()->first;
    
    return answer;
}

정렬 알고리즘을 이용한 코드

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

using namespace std;

string solution(vector<string> participant, vector<string> completion) {
    string answer = "";
    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[participant.size() - 1];
    //return answer;
}

이 코드는 단순하게 sort함수를 이용해서 하나씩 비교해가며 찾는 방식이다.

어떻게 보면 이 방법이 가장 단순하고 쉽지만, 위에서 말했다시피 해시를 이용해서 풀어보고 싶었다.

unordered_map이란

unordered_map은 C++에서 제공하는 핵심 자료구조 중 하나로, 키-값 쌍을 빠르게 저장하고 검색할 수 있도록 도와준다. 마치 사전처럼 생각하면 쉽다. 단어(키)를 입력하면 정의(값)를 찾아볼 수 있다.

unordered_map의 특징

• 빠른 검색: 해시 테이블을 사용하여 키를 기반으로 값을 빠르게 찾아낼 수 있습니다. 평균적으로 O(1)의 시간 복잡도를 제공한다.
• 중복 허용 안 함: 같은 키를 가진 값은 하나만 저장할 수 있다.
• 순서 없음: 데이터가 저장된 순서는 보장되지 않는다.
• 효율적인 메모리 사용: 비슷한 크기의 다른 자료구조에 비해 메모리를 효율적으로 사용한다.

unordered_map vs. map

unordered_map과 비슷한 자료구조로 map이 있다. 두 자료구조 모두 키-값 쌍을 저장하지만, 몇 가지 중요한 차이점이 있다.

구분 unordered_map map

검색 속도	O(1)	O(log N)
중복 허용	안 함	안 함
순서	없음	있음
메모리 사용	효율적	비교적 비효율적

unordered_map은 빠른 검색 속도가 가장 큰 장점입니다. 데이터의 크기가 커질수록 검색 속도 차이가 더욱 확대된다. 반면, map은 데이터를 순서대로 유지해야 하는 경우 유용하다.

unordered_map 사용 예시 코드

C++

#**include** <iostream>#**include** <unordered_map>int main() {
  // unordered_map 선언
  std::unordered_map<std::string, int> my_map;

  // 데이터 추가
  my_map["apple"] = 100;
  my_map["banana"] = 200;
  my_map["orange"] = 300;

  // 값 찾기
  int apple_price = my_map["apple"];
  std::cout << "Apple price: " << apple_price << std::endl;

  // 데이터 존재 여부 확인
  if (my_map.find("grape") != my_map.end()) {
    std::cout << "Grape exists" << std::endl;
  } else {
    std::cout << "Grape does not exist" << std::endl;
  }

  return 0;
}