캐시 - 카카오 기출

programmers.co.kr/learn/courses/30/lessons/17680

코딩테스트 연습 - [1차] 캐시

 

#include <string>
#include <vector>
#include <iostream>
#include <boost/algorithm/string.hpp>
#include <map>
using namespace std;

int solution(int cacheSize, vector<string> cities) {
    int answer = 0;
   // map<string,bool>cache;
    vector<string>v;
    map<string,bool>m;

    if(cacheSize==0){return cities.size()*5;}
 for(int i=0; i<cities.size(); i++){   
     string str = cities[i];
     boost::algorithm::to_lower(str);   // string 대소문자 바꾸는 라이브러리 
     cities[i]=str;
    if(m[cities[i]]==false){
    if(v.size()==cacheSize){ if(v.size()>0){ m[v[0]]=false; v.erase(v.begin());}}
    v.push_back(cities[i]);
    m[cities[i]]=true;
    answer+=5;
    }
    else{
        for(int j=0; j<v.size(); j++){
            if(cities[i]==v[j]){
                v.erase(v.begin()+j);
                v.push_back(cities[i]);
                break;
            }
        }

        answer+=1;
      }
 }
    return answer;
}

 

어떤 알고리즘? 무슨 논리로 그알고리즘을 사용?

- 해시 맵을 이용해서 캐시에 문자열이 드렁있는지의 여부를 판단하고 vector을 이용해서 한번 hit한경우 다시 해당 문자열을 뒤로 보냄. 

 

헷갈렸던점?

- 문자열 전체를 소문자로 만드는 것을 다 구현해야할 줄 알았는데 라이브러리가 있었다.

- 소문자 혹은 대문자로 만드는 라이브러리가 boost/algorithm/string.hpp 에 있다.

 

<JAVA>

import java.util.*;
class Solution {
    
    
    
    
    public int solution(int cacheSize, String[] cities) {
        int answer = 0;
        LinkedList<String>list = new LinkedList<>();
        
        int cnt = 0;
        
        for(int i=0;i<cities.length; i++){
            
            String s = cities[i];
            cities[i]= s.toLowerCase(); //소문자로 만들기: s.toLowerCase() 대문자로 만들기 s.toUpperCase()
            
        }
        
        for(int i=0;i<cities.length; i++){
            String city = cities[i];
            boolean toggle = false;
            for(int j=0; j<list.size(); j++){
                if(list.get(j).equals(city)){ // String 비교할때는 꼭 equals 쓰기!!
                    toggle = true;
                    list.remove(j);
                    list.add(city);
                    answer+=1;
                    break;
                }
            }
            
            if(!toggle){
                if(cacheSize==0){answer+=5; continue;}
                if(cnt<cacheSize){
                    list.add(city);
                    cnt++;
                }
                else{
                    list.remove(0);
                    list.add(city);
                }
                answer+=5;
            }    
       //     System.out.println(answer);
        }        
        
        
        return answer;
    }
}

- 소문자로 만들기: s.toLowerCase()

- 대문자로 만들기 s.toUpperCase()

-  String 비교할때는 꼭 equals 쓰기!!