Level 1. 완주하지 못한 선수 중복 키를 저장할 수 있고 정렬을 유지하지 않는 unordered_multiset을 이용해 해결했다. 완주한 참가자를 모두 제거한 후 마지막 남은 참가자가 완주에 실패한 참가자이다. #include #include #include using namespace std; string solution(vector participant, vector completion) { unordered_multiset umset(participant.begin(), participant.end()); for (string& s : completion) umset.erase(umset.find(s)); return *umset.begin(); } 정렬하여 다른 이름이 나올 때까지 비교하는..

lower_bound(val): val보다 크거나 같은 첫 반복자 위치를 반환한다. upper_bound(val): val보다 큰 첫 반복자 위치를 반환한다. 둘 모두 이진 검색을 사용하므로 정렬된 상태에서만 사용해야 한다. #include #include #include using namespace std; void main() { vector v = {6, 3, 1, 4, 7, 6, 2, 1}; cout

erase() 함수는 보통 하나의 원소만 삭제해서 multiset에서도 그런 줄 알았는데 아니었다. multiset, multimap에서 erase() 함수는 해당 키를 갖는 원소를 모두 삭제한다. #include #include #include using namespace std; void main() { multiset mset{1, 4, 2, 1, 5, 3}; unordered_multimap ummap{{1, 0}, {4, 0}, {2, 0}, {1, 0}, {5, 0}, {3, 0}}; mset.erase(1); ummap.erase(1); for (int e : mset) cout

Level 1. 과일 장수 사과를 점수의 역순으로 정렬한 후 앞에서부터 m개 중 가장 마지막(최저 점수) 사과를 기준으로 가격을 계산하고 해당 m개를 삭제한다. 하지만, 이 방법은 시간 초과가 발생했다. #include #include #include using namespace std; int solution(int k, int m, vector score) { int answer = 0; sort(score.rbegin(), score.rend()); while (m

코딩 테스트를 위한 자료 구조와 알고리즘 with C++ 병합 정렬 분할-정복-결합 과정을 거치는 분할 정복 알고리즘이다. 전체 데이터의 일부를 가져와 정렬한 후 외부에 다시 저장하는 외부 정렬(External Sorting) 알고리즘이다. O(nlog n) 복잡도를 갖는다. 병합 정렬 과정 분할: 부분 집합의 크기가 1이 될 때까지 분할한다. 정복: 나눠진 부분 집합을 오름차순이 되도록 다시 결합한다. 결합: 기존 집합의 크기와 같아질 때까지 2. 정복부터 반복한다. #include #include using namespace std; template vector merge(vector& v1, vector& v2) { vector m; auto it1 = v1.begin(); auto it2 = v2..

전에 알고리즘 스터디를 할 때 map의 키 존재 여부를 0으로 확인하는 것이 안전한지, 컴파일러에 따라 다른 것은 아닌지에 대해 의논했던 적이 있다. map default values std::map mapy; ++mapy[5]; Is it safe to assume that mapy[5] will always be 1? I mean, will mapy[5] always get the default value of 0 before '++', even if not explicitly declared, as... stackoverflow.com 위 쓰레드에 따르면 map의 [] 연산자는 키가 존재하지 않을 경우 value_type(std::move(x), T())을 통해 값을 삽입한다. T()는 void를 ..