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

pa324·2019년 11월 20일
1

문제

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은 헤더파일에 있다.

  • 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;
}                 
                                           
profile
안녕하세요

2개의 댓글

comment-user-thumbnail
2020년 5월 29일

안녕하세요! 프로그래머스 문제 풀면서 들어왔습니다.
모범답안을 정말 완벽하고 체계적으로 정리해주셨는데 약간의 벌레(^^)가 있어요...
일단, 사용되지 않은 int num이 있고요, 본문의 코드에서 i <= participant.size() 대신 i < participant.size()로 연산자를 바꾸어야 좀 더 안전한 코딩이 될 것 같아요.
물론 문제상으로는 completion에 무조건 1개 적은 값들이 입력되고 위의 코드로 오류없이 정확하게 정답을 맞추겠지만, 벡터에 5개의 스트링이 있는 경우 participant.size()는 5인데 participant[5]를 읽는 순간 런타임 오류가 납니다. 배열 번호는 0부터 4까지 가능하니까요...
문제 풀러 오는 사람들도 있지만 이런 블로그를 통해 C++를 익히는 사람들이 있으니까요~ 마지막줄에 ""라는 리턴값을 추가로 주는 것도 뽀너쓰 안전장치가 될 것 같아요. (물론 문제에 맞게 하나 빠진 벡터가 입력되면 실행되지 않는 줄이지만요...)

1개의 답글