카카오 캐시

skyepodium·2020년 5월 3일
CJavaJavaScriptpython카카오카카오 캐시캐시
2

2018 KAKAO BLIND RECRUITMENT 1차

목록 보기
3/4
post-thumbnail

문제

LRU를 몰랐어도 빠르게 파악하고 구현하는 문제

  1. 캐시 크기 ( 0 <= cacheSize <= 30 )

  2. 도시의 수 ( 0 <= cities <= 10만 )

  3. 도시의 이름 ( 0<= 도시 이름 길이 <= 20)

  4. 도시 이름은 대소문자를 구분하지 않는다.

  5. 캐시 교체알고리즘은 LRU을 사용한다.

  6. cache hit - 1, cache miss - 5

문제 링크

1. 첫인상

LRU가 뭐지? 페이지 교체 알고리즘은 뭐지?, 캐시는 뭐지?

침착하게, 흔들리지 말고 온라인 테스트이니까 검색 찬스를 사용합니다.

사실, LRU를 모른다는 점을 제외하고는 문제가 그렇게 어려워보이지는 않습니다.

2. 문제 쪼개기

  1. 입력
  2. 입력된 도시 이름 - 모두 소문자로 바꾸기
  3. LRU 구현
  4. 반환

1, 4번은 일반적이기 때문에 2, 3번을 집중해서 보겠습니다.

3. LRU

1) 정의

사용한지 가장 오래된 것을 버리는 알고리즘 (Least Recently Used)

2) 과정

크게 3개의 경우가 있습니다.

1, 2번 경우만 고려하면 가장 먼저 들어간것이 가장 나중에 나오는 큐 라고 여겨집니다.

다만, 3번의 경우와 같이 먼저 들어갔어도 제일 최신으로 상태가 변경되는 경우가 있습니다.

따라서, 기본 라이브러리의 큐를 그대로 사용하기 보다는 조금 변형해서 사용합니다.

3) 자료구조

저는 배열을 큐 처럼 사용합니다.
이런 경우 위의 1, 2번을 해결할 수 있습니다.

다만, 3번의 경우 다음과 같이 처리합니다.
1) 앞에서 부터 같은 것이 있는지 반복문으로 탐색
2) 저장한 인덱스 기준 한칸신 당겨줍니다.
3) 그리고, 삽입된 요소를 배열의 제일 뒤에 넣어줍니다.

그리고, 지극히 주관적이고 제 경험적인 의견입니다만.

문제를 풀기 위해 set을 사용하고자 할 수 있는데요.

알고리즘 문제에서 왠만해서는 set안쓰게 하더라구요.

오히려 쓰면 더 불편한 경우도 많고해서요.

4. 소문자로 바꾸기

아스키 코드를 사용해서 바꿔주었습니다.

/*
    대문자를 소문자로 변경하는 함수
    아스키코드 사용
*/
string to_lowercase(string name) {
    string result = name;

    int name_size = (int)result.size();
    for(int i=0; i< name_size; i++){
        /*
            만약 아스키 코드 값이 97보다 작으면 대문자 이기 때문에
            32를 더해서 대문자로 만들어줍니다.
            a - 97
            A - 65
        */
        if(result[i] < 97) result[i] += 32;
    }

    return result;
}

5. 시간 복잡도 계산

n: 도시의 수, m: 캐시의 크기, k: 도시 이름의 길이

도시 1개식 반복문으로 탐색 O(n) * (LRU + 소문자로 바꾸기) O(m+k)

O(n(m+k))

m ( 0 <= cacheSize <= 30 )

n ( 0 <= cities <= 10만 )

k ( 0<= 도시 이름 길이 <= 20)

시간 복잡도 = 50 * 10만 = 500만

1억에 1초걸리기 때문에 시간안에 충분히 풀 수 있습니다.

6. 전체 코드

1) c++

#include <string>
#include <vector>
#define max_int 31
using namespace std;

/*
    시간 복잡도: O((m+k)n) n: 도시의 수, m: 캐시의 크기, k: 도시 이름의 길이
    공간 복잡도: O(m)
    사용한 알고리즘: 반복문(LRU 구현에 사용)
    사용한 자료구조: 배열 (캐시 저장에 사용)
*/

/*
    대문자를 소문자로 변경하는 함수
    아스키코드 사용
*/
string to_lowercase(string name) {
    string result = name;

    int name_size = (int)result.size();
    for(int i=0; i< name_size; i++){
        /*
            만약 아스키 코드 값이 97보다 작으면 대문자 이기 때문에
            32를 더해서 대문자로 만들어줍니다.
            a - 97
            A - 65
        */
        if(result[i] < 97) result[i] += 32;
    }

    return result;
}

int solution(int cacheSize, vector<string> cities) {
    int answer = 0;

    // 도시 이름을 저장할 캐시의 자료구조로 배열 생성
    string a[max_int];

    // 현재 캐시가 어느만큼 차있는지 알기 위한 인덱스
    int idx = 1;

    int city_size = (int)cities.size();
    for(int i=0; i < city_size; i++) {
        /*
            대소문자 구분하지 않기 때문에
            도시 이름은 전부 소문자로 변경시켜줍니다.
        */
        string city_name = to_lowercase(cities[i]);

        // cache hit, cache miss 여부를 체크하기 위한 변수 is_exist
        bool is_exist = false;
        // cache hit인 경우 어떤 캐시가 최근에 사용되었는지 체크하기 위한 인덱스
        int start_idx = 1;
        // 캐시 사이즈가 0인 경우 캐시를 검사하지 않는다.
        if(cacheSize != 0) {
            for(int j=1; j<=idx; j++) {
                if(city_name == a[j]) {
                    is_exist = true;
                    // 가장 최근에 사용된 캐시의 인덱스를 저장해줍니다.
                    start_idx = j;
                    break;
                }
            }
        }

        /*
          cache hit 인 경우 += 1
          cache miss 인 경우 += 5
        */
        if(is_exist) answer += 1;
        else  answer += 5;

        // 1) 만약 캐시가 꽉 찼다면
        if(idx == cacheSize) {
            /*
                최근에 사용된 캐시 부터 끝까지 한칸씩 앞으로 밀어줍니다.
                최근에 사용된 인덱스가 없으면 1부터 시작합니다.
            */
            for(int i=start_idx; i < idx; i++) {
                a[i] = a[i+1];
            }
            // 최근에 사용된 캐시는 제일 뒤에 넣어줍니다.
            a[idx] = city_name;
        }
            // 2) 아직 캐시가 비어있다면
        else if(idx < cacheSize){
            // 인덱스를 1증가시키고 도시 이름을 넣어줍니다.
            idx++;
            a[idx] = city_name;
        }
    }

    return answer;
}

2) java

/*
    시간 복잡도: O((m+k)n) n: 도시의 수, m: 캐시의 크기, k: 도시 이름의 길이
    공간 복잡도: O(m)
    사용한 알고리즘: 반복문(LRU 구현에 사용)
    사용한 자료구조: 배열 (캐시 저장에 사용)
*/
class Solution {
    /*
        대문자를 소문자로 변경하는 함수
        아스키코드 사용
    */
    public String to_lowercase(String name) {
        String result = "";

        int name_size = name.length();
        for(int i=0; i< name_size; i++){
            /*
                만약 아스키 코드 값이 97보다 작으면 대문자 이기 때문에
                32를 더해서 대문자로 만들어줍니다.
                a - 97
                A - 65
            */
            char c = (char)name.charAt(i);
            if(name.charAt(i) < 97)  c += 32;

            result += c;
        }

        return result;
    }

    public int solution(int cacheSize, String[] cities) {
        int answer = 0;

        // 도시 이름을 저장할 캐시의 자료구조로 배열 생성
        String a[] = new String[cacheSize + 2];

        // 현재 캐시가 어느만큼 차있는지 알기 위한 인덱스
        int idx = 1;

        int city_size = cities.length;
        for(int i=0; i < city_size; i++) {
            /*
                대소문자 구분하지 않기 때문에
                도시 이름은 전부 소문자로 변경시켜줍니다.
            */
            String city_name = to_lowercase(cities[i]);

            // cache hit, cache miss 여부를 체크하기 위한 변수 is_exist
            Boolean is_exist = false;
            // cache hit인 경우 어떤 캐시가 최근에 사용되었는지 체크하기 위한 인덱스
            int start_idx = 1;
            for(int j=1; j<=idx; j++) {
                if(city_name.equals(a[j])) {
                    is_exist = true;
                    // 가장 최근에 사용된 캐시의 인덱스를 저장해줍니다.
                    start_idx = j;
                    break;
                }
            }

            /*
              cache hit 인 경우 += 1
              cache miss 인 경우 += 5
            */
            if(is_exist) answer += 1;
            else  answer += 5;

            // 1) 만약 캐시가 꽉 찼다면
            if(idx == cacheSize) {
                /*
                    최근에 사용된 캐시 부터 끝까지 한칸씩 앞으로 밀어줍니다.
                    최근에 사용된 인덱스가 없으면 1부터 시작합니다.
                */
                for(int j=start_idx; j < idx; j++) {
                    a[j] = a[j+1];
                }
                // 최근에 사용된 캐시는 제일 뒤에 넣어줍니다.
                a[idx] = city_name;
            }
            // 2) 아직 캐시가 비어있다면
            else if(idx < cacheSize){
                // 인덱스를 1증가시키고 도시 이름을 넣어줍니다.
                idx++;
                a[idx] = city_name;
            }
        }

        return answer;
    }
}

3) python

'''
    시간 복잡도: O((m+k)n) n: 도시의 수, m: 캐시의 크기, k: 도시 이름의 길이
    공간 복잡도: O(m)
    사용한 알고리즘: 반복문(LRU 구현에 사용)
    사용한 자료구조: 배열 (캐시 저장에 사용)
'''

'''
    대문자를 소문자로 변경하는 함수
    아스키코드 사용
'''

def to_lowercase(name):
    result = "";

    name_size = len(name)
    for i in range(name_size):

        c = ord(name[i])
        if c < 97: c += 32

        result += chr(c)

    return result;


def solution(cacheSize, cities):
    answer = 0

    a = [" " for _ in range(cacheSize + 2)]

    idx = 1

    for city_name in cities:
        city_name = to_lowercase(city_name)

        is_exist = False
        start_idx = 1
        if cacheSize != 0:
            for j in range(1, idx+1):
                if a[j] == city_name:
                    is_exist = True
                    start_idx = j
                    break
        
        if is_exist: answer += 1
        else: answer += 5

        if idx == cacheSize:
            for i in range(start_idx, idx+1):
                a[i] = a[i+1]
            
            a[idx] = city_name
        
        elif idx < cacheSize:
            idx += 1
            a[idx] = city_name

    return answer

4) javascript

/*
    시간 복잡도: O((m+k)n) n: 도시의 수, m: 캐시의 크기, k: 도시 이름의 길이
    공간 복잡도: O(m)
    사용한 알고리즘: 반복문(LRU 구현에 사용)
    사용한 자료구조: 배열 (캐시 저장에 사용)
*/

/*
    대문자를 소문자로 변경하는 함수
    아스키코드 사용
*/
function to_lowercase(name) {
    let result = "";

    let name_size = name.length
    for(let i=0; i< name_size; i++){
        /*
            만약 아스키 코드 값이 97보다 작으면 대문자 이기 때문에
            32를 더해서 대문자로 만들어줍니다.
            a - 97
            A - 65
        */
        let c = name.charCodeAt(i)
        if(c < 97) {
            c += 32;
        }
        
        result += String.fromCharCode(c)
    }

    return result;
}

function solution(cacheSize, cities) {
    let answer = 0;

    // 도시 이름을 저장할 캐시의 자료구조로 배열 생성
    let a = [];

    // 현재 캐시가 어느만큼 차있는지 알기 위한 인덱스
    let idx = 1;

    let city_size = cities.length;
    for(let i=0; i < city_size; i++) {
        /*
            대소문자 구분하지 않기 때문에
            도시 이름은 전부 소문자로 변경시켜줍니다.
        */
        let city_name = to_lowercase(cities[i]);

        // cache hit, cache miss 여부를 체크하기 위한 변수 is_exist
        let is_exist = false;
        // cache hit인 경우 어떤 캐시가 최근에 사용되었는지 체크하기 위한 인덱스
        let start_idx = 1;
        if(cacheSize != 0) {
            for(let j=1; j<=idx; j++) {
                if(a[j] == city_name) {
                    is_exist = true;
                    // 가장 최근에 사용된 캐시의 인덱스를 저장해줍니다.
                    start_idx = j;
                    break;
                }
            }            
        }


        /*
          cache hit 인 경우 += 1
          cache miss 인 경우 += 5
        */
        if(is_exist) answer += 1;
        else  answer += 5;

        // 1) 만약 캐시가 꽉 찼다면
        if(idx == cacheSize) {
            /*
                최근에 사용된 캐시 부터 끝까지 한칸씩 앞으로 밀어줍니다.
                최근에 사용된 인덱스가 없으면 1부터 시작합니다.
            */
            for(let i=start_idx; i < idx; i++) {
                a[i] = a[i+1];
            }
            // 최근에 사용된 캐시는 제일 뒤에 넣어줍니다.
            a[idx] = city_name;
        }
            // 2) 아직 캐시가 비어있다면
        else if(idx < cacheSize){
            // 인덱스를 1증가시키고 도시 이름을 넣어줍니다.
            idx++;
            a[idx] = city_name;
        }
    }

    return answer;
}    let c = name.charCodeAt(i)
        if(c < 97) {
            c += 32;
        }
        
        result += String.fromCharCode(c)
    }

    return result;
}

function solution(cacheSize, cities) {
    let answer = 0;

    // 도시 이름을 저장할 캐시의 자료구조로 배열 생성
    let a = ["", "", "", ""];

    // 현재 캐시가 어느만큼 차있는지 알기 위한 인덱스
    let idx = 1;

    let city_size = cities.length;
    for(let i=0; i < city_size; i++) {
        /*
            대소문자 구분하지 않기 때문에
            도시 이름은 전부 소문자로 변경시켜줍니다.
        */
        let city_name = to_lowercase(cities[i]);

        // cache hit, cache miss 여부를 체크하기 위한 변수 is_exist
        let is_exist = false;
        // cache hit인 경우 어떤 캐시가 최근에 사용되었는지 체크하기 위한 인덱스
        let start_idx = 1;
        for(let j=1; j<=idx; j++) {
            if(a[j] == city_name) {
                is_exist = true;
                // 가장 최근에 사용된 캐시의 인덱스를 저장해줍니다.
                start_idx = j;
                break;
            }
        }

        /*
          cache hit 인 경우 += 1
          cache miss 인 경우 += 5
        */
        if(is_exist) answer += 1;
        else  answer += 5;

        // 1) 만약 캐시가 꽉 찼다면
        if(idx == cacheSize) {
            /*
                최근에 사용된 캐시 부터 끝까지 한칸씩 앞으로 밀어줍니다.
                최근에 사용된 인덱스가 없으면 1부터 시작합니다.
            */
            for(let i=start_idx; i < idx; i++) {
                a[i] = a[i+1];
            }
            // 최근에 사용된 캐시는 제일 뒤에 넣어줍니다.
            a[idx] = city_name;
        }
            // 2) 아직 캐시가 비어있다면
        else if(idx < cacheSize){
            // 인덱스를 1증가시키고 도시 이름을 넣어줍니다.
            idx++;
            a[idx] = city_name;
        }
    }

    return answer;
}
profile
skyepodium
callmeskye
이전 포스트

카카오 다트 게임

다음 포스트

카카오 뉴스 클러스터링

0개의 댓글