문제

https://programmers.co.kr/learn/courses/30/lessons/42576?language=cpp

c++ STL 정리

c++의 vector자료형이 함수의 파라미터로 주어지기 때문에, vector자료형을 먼저 정리해 보겠다.

vector

vector는 array와 비슷하지만, 크기가 정해지지 않은 Linked-List와 비슷한 자료형이다. 모든 원소를 동적으로 생성/삭제 할 수 있다.

vector 선언

include <vector> 를 통해서 vector stl을 사용할 수 있다. 선언은 vector<type> name; 형태로 하면 된다.

vector 멤버함수

추가/삭제
  • push_back(data)
    • 맨 뒤에 data를 추가하는 함수
  • pop_back()
    • 제일 뒤에있는 원소를 삭제하는 함수
조회
  • vector[i]

    • i번째 인덱스에 위치한 원소 반환
  • vector.at(i)

    • i번째 인덱스에 위차한 원소를 반환
  • vector.front()

    • 맨 앞에 위치한 원소 반환
  • vector.back()

    • 맨 뒤에 위치한 원소 반환
  • size()

    • 벡터의 크기 반환
  • empty()

    • 벡터가 비어 있는지 boolean형태로 반환

Map

  • map 컨테이너는 원소를 key,value 쌍으로 저장한다.
  • set처럼 원소의 key는 컨테이너에 중복 저장될 수 없고, 중복 key를 저장해야 한다면 multimap을 사용해야 한다.
  • map<key,value> 형태로 선언한다. (key,value를 pair형태로)

멤버 함수

iterator
  • begin()
    • 시작 iterator반환
  • end()
    • 끝 iterator 반환
      추가/삭제
  • insert(make_pair(key,value))
    • 원소를 pair형태로 추가
  • erase(key)
    • key값에 해당하는 원소를 삭제
  • clear()
    • 맵의 원소를 모두 삭제
조회
  • find(key)

    • key값에 해당하는 iterator반환
  • count(key)

    • key값에 해당하는 원소(value들)의 개수 반환
      기타
  • empty()

    • 맵이 비어 있으면 true, 아니면 false
  • size()

    • 맵 원소들의 수를 반환

    sort algorithm

  • sort algorithm은 <algorithm> 헤더파일에 있다.

  • sort(start,end)를 이용하여 인자를 오름차순으로 정렬해 준다.

  • quick sort를 기반으로 함수가 구현되어 있어, nlogn시간 복잡도를 가진다.

풀이

정렬 활용

participant,completion을 문자열 순서대로 정렬을 시킨다. 그리고 원소를 차례차례 비교하다가 일치하지 않는 값이 나온다변 완주하지 못한 선수가 된다.

map 활용

map을 활용해서, 완주한 목록을 key,value값으로 저장한다음 participant값이 map안에 포함되어 있는지 확인하는 방식으로도 구현할 수 있다.

코드

[정렬 활용]


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

string solution(vector<string> participant, vector<string> completion) {

    std::sort(participant.begin(), participant.end());
    std::sort(completion.begin(),completion.end());

    int num = 0;

    for(int i = 0 ; i <= participant.size(); i++) {
        if(participant[i] != completion[i]) {
            return participant[i];
        }
    }

}

[map 활용]


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

using namespace std;

string solution(vector<string> participant, vector<string> completion) {
    string answer = "";
    unordered_map<string, int> strMap;
    for(auto elem : completion)
    {
        if(strMap.end() == strMap.find(elem))
            strMap.insert(make_pair(elem, 1));
        else
            strMap[elem]++;
    }

    for(auto elem : participant)
    {
        if(strMap.end() == strMap.find(elem))
        {
            answer = elem;
            break;
        }
        else
        {
            strMap[elem]--;
            if(strMap[elem] < 0)
            {
                answer = elem;
                break;
            }
        }
    }
    return answer;
}