[2021.03.28] 코딩테스트준비

이진탐색

• 파라메트릭 서치 : 최적의 해를 구할 때, 결정문제(예, 아니오)로 바꾸어 해결
  - 예) 가래떡 문제.. 선형적이 아닌 2진 탐색으로 해결
• 정렬된 벡터에서 4의 갯수, 5의 갯수를 구할 떄, lower_boud/upper_bound를 확인하여 빼준다.

2018 코딩테스트 문제 3

#include <iostream>
#include <vector>
#include <string>
#include <list>

using namespace std;

list<string> cache;

int get_data(string city, int cacheSize)
{
    int time;

    auto it = find(cache.begin(), cache.end(), city);
    if (it != cache.end()) { // exist
        time = 1;
        cache.erase(it);
    }
    else {
        time = 5;
    }
    cache.push_back(city);

    if (cache.size() > cacheSize) {
        cache.erase(cache.begin());
    }

    return time;
}

int main()
{
    int cacheSize=2;
    vector<string> cities = {"Jeju", "Pangyo", "Seoul", "NewYork", "LA",
        "SanFrancisco", "Seoul", "Rome", "Paris", "Jeju", "NewYork", "Rome"};

    int sum = 0;
    for (int i = 0; i < cities.size(); i++) {
        sum += get_data(cities[i], cacheSize);
    }

    cout << sum << endl;

    return 0;
}