첫번째 소스코드

• 큐와 set을 이용한...시간복잡도 오래걸리기도 했다.
  채점 : 50점 나옴.

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

int solution(int cacheSize, vector<string> cities) {
    int answer = 0;
    
    queue<string>q;
    unordered_set<string>check;
    
    for(int i = 0; i < cities.size(); i++)
    {       
        transform(cities[i].begin(), cities[i].end(), cities[i].begin(), ::tolower);
       
        if(q.size() == cacheSize)
        {        
            if(check.find(cities[i]) != check.end())
            {
                answer += 1;
            }
            else
            {
                check.erase(q.front());
                answer += 5;
                check.insert(cities[i]);
            }
            
            q.pop();
        }
        else
        {
            //발견하지 못한다면 새롭게 추가하는 것이다. 
            if(check.find(cities[i]) == check.end())
            {
                check.insert(cities[i]);
                answer += 5;
            }
            //존재할 경우
            else 
            {
                answer += 1;
            }
        }
        
        q.push(cities[i]);
    }
    
    
    
    return answer;
}

배울점

: erase를 해야하기 때문에 vector로 하기에 망설였다.
1) erase 를 맨앞과 뒤에서 하면 시간복잡도는?
O(n) 이지만 해당 문제에서는

cacheSize는 정수이며, 범위는 0 ≦ cacheSize ≦ 30 이다.
이러한 조건이 있으므로 erase 하는데 최대 30밖에 안걸렸다.

-> 문제를 잘 읽고 erase 쓸지 안쓸지 판단했어야 했다.
=> 그리고 너무 고민하지 말고, 일단 풀어나가자. 풀고 부분 점수 맞는게
나을 수 있다.

2) string 소문자, 대문자 변환 공부 및 정리하자.

vector로 풀기

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int solution(int cacheSize, vector<string> cities) {
    int answer = 0;
    
    if(cacheSize == 0)
        return cities.size() * 5;
    
    for(string &city : cities)
    {
        for(int j = 0; j < city.size(); j++)
        {
            city[j] = tolower(city[j]);
        }
    }
    
    vector<string> v;
    
    for(int i = 0; i < cities.size(); i++)
    {       
        
        auto iter = find(v.begin(), v.end(), cities[i]);
        
        //v.find 가 아니다.
        
        //cache hit
        if(iter != v.end())
        {
            answer++;
            v.erase(iter);
        }
        //cache miss
        else
        {
            answer += 5;
            
            if(v.size() == cacheSize)
                v.erase(v.begin());
        }
      
        v.emplace_back(cities[i]);
    }
    
    
    
    return answer;
}

삽입 정렬로 풀기