기록공간

우선 해결방법은 컨테이너에 마라톤 선수의 이름과 정수형 변수를 보관하는 것이다. 참가한 마라톤 선수를 원소로 집어넣을때 정수형 변수를 1 증가시킨다. 그 작업이 끝나면, 이제 완주한 마라톤 선수를 컨테이너에서 찾아 그 원소의 정수형 변수를 1 감소시킨다. 그리고 컨테이너를 순회돌며 정수형 변수가 0이 아닌 마라톤 선수 이름이 정답이 된다. STL의 컨테이너 형식으로 어떤 것을 쓸건지에 따라서 알고리즘의 시간 복잡도가 바뀌게 된다. 우선 첫번째는 STL의 map 컨테이너를 사용하는 것이다. map 컨테이너는 이진 탐색 트리(binary search tree)의 원리를 이용한 컨테이너로 항상 원소의 키값을 기준으로 정렬된 상태를 유지한다. 트리 검색 특성상 원소의 갯수가 N개 일때 검색 시간 복잡도는 O(l..

정렬 조건을 정하여 정렬하는 문제이다. 위 설명처럼 순열을 모두 구해서 내림차순으로 정렬하는 방법을 생각해 볼 수 있다. 값은 정확하게 나오지만 순열의 개수는 (numbers의 원소의 개수)! (팩토리얼)이기 때문에 원소의 갯수가 많을수록 기하급수적으로 많아진다. 결국 시간 초과가 되므로 이 방법은 쓸 수 없다. (STL에서 제공하는 next_permutation을 사용하면 순열을 쉽게 구할 수 있으므로 한번 시도해보는 것도 나쁘지 않다) 정렬을 내림차순으로 하더라도 [6, 10, 2] 같은 경우 [10, 6, 2]로 1062가 되므로 가장 큰 수를 만족하지 못한다. 하지만 원소들을 string으로 바꾸고 서로의 조합을 통해 비교해서 정렬하면 어떨까? 예를 들어 [6, 10, 2]가 있다면 이를 stri..