[프로그래머스] 1. 로또의 최고 순위와 최저 순위(Lv1), 2. [1차]캐시(Lv2), 3. 2xn 타일링(Lv2)

Lv. 1: 로또의 최고 순위와 최저 순위✍️

---

문제 설명

순위	당첨 내용
1	6개 번호 모두 일치
2	5개 번호 일치
3	4개 번호 일치
4	3개 번호 일치
5	2개 번호 일치
6	그 외

로또를 구매한 민우는 당첨 번호 발표일을 학수고대하고 있었습니다. 하지만, 민우의 동생이 로또에 낙서를 하여, 일부 번호를 알아볼 수 없게 되었습니다. 당첨 번호 발표 후, 민우는 자신이 구매했던 로또로 당첨이 가능했던 최고 순위와 최저 순위를 알아보고 싶어 졌습니다. 알아볼 수 없는 번호를 0으로 표기했을 때, 민우가 당첨 가능한 최고 순위와 최저 순위를 차례대로 배열에 담아 반환하는 함수를 완성하세요.

제한사항

• lottos는 길이 6인 정수 배열입니다.
• lottos의 모든 원소는 0 이상 45 이하인 정수입니다.
• 0은 알아볼 수 없는 숫자를 의미합니다.
• 0을 제외한 다른 숫자들은 lottos에 2개 이상 담겨있지 않습니다.
• lottos의 원소들은 정렬되어 있지 않을 수도 있습니다.
• win_nums은 길이 6인 정수 배열입니다.
• win_nums의 모든 원소는 1 이상 45 이하인 정수입니다.
• win_nums에는 같은 숫자가 2개 이상 담겨있지 않습니다.
• win_nums의 원소들은 정렬되어 있지 않을 수도 있습니다.

나의 답안

function solution(lottos, win_nums) {
    let count = 0, countZero = 0;
    let chance = [];
    
    let rank = [6, 5, 4, 3, 2, 1];
    for(let i = 0; i < lottos.length; i++) {
        if(lottos[i] === 0) countZero++;
        for(let j = 0; j < win_nums.length; j++) {
            if(lottos[i] === win_nums[j]) count++; 
        }
    }
    if(count === 0 && countZero === 0) return [6, 6];
    if(count === 0 || count === 1) chance.push(rank[count + countZero - 1], 6);
    else chance.push(rank[count + countZero - 1], rank[count - 1]); 

    return chance;
}

접근 방식

• 당첨 번호는 순서(index)와 상관없이 일치하기만 하면 되기 때문에 이중for문으로 민우의 번호와 실제 당첨번호를 비교하고, 일치하는 경우에는 count++ 해준다.
• 민우 번호 중 알아볼 수 없는 숫자 0이 나올 때마다 countZero++ 해준다.
• 누적된 count수로 인덱스로 쉽게 사용하기 위해 등수를 내림차순으로 rank라는 배열에 담아준다.
• 0의 개수에 따라 최저/최고 순위를 chance라는 배열에 담아주고 반환한다.
• 다만, 예외처리를 별도로 해주어야한다.
  1. 맞춘 숫자도, 0이 하나도 없는 경우 최저 순위도 6등, 최고 순위도 6등이다.
  2. 맞춘 숫자가 0개이거나 1개일 때는 똑같이 6등이다.
  

다른 사람 풀이

function solution(lottos, win_nums) {
    const rank = [6, 6, 5, 4, 3, 2, 1];

    let minCount = lottos.filter(v => win_nums.includes(v)).length;
    let zeroCount = lottos.filter(v => !v).length;

    const maxCount = minCount + zeroCount;

    return [rank[maxCount], rank[minCount]];
}

• 접근 방식은 비슷했지만 for문보다는 여러 메서드를 사용해서 훨씬 짧은 코드를 작성했다.
• rank에 6을 두 번 넣어서 예외처리를 훨씬 효율적으로 한 부분이 인상 깊었다.

Lv. 2: [1차] 캐시✍️

---

문제 설명

지도개발팀에서 근무하는 제이지는 지도에서 도시 이름을 검색하면 해당 도시와 관련된 맛집 게시물들을 데이터베이스에서 읽어 보여주는 서비스를 개발하고 있다. 이 프로그램의 테스팅 업무를 담당하고 있는 어피치는 서비스를 오픈하기 전 각 로직에 대한 성능 측정을 수행하였는데, 제이지가 작성한 부분 중 데이터베이스에서 게시물을 가져오는 부분의 실행시간이 너무 오래 걸린다는 것을 알게 되었다. 어피치는 제이지에게 해당 로직을 개선하라고 닦달하기 시작하였고, 제이지는 DB 캐시를 적용하여 성능 개선을 시도하고 있지만 캐시 크기를 얼마로 해야 효율적인지 몰라 난감한 상황이다. 어피치에게 시달리는 제이지를 도와, DB 캐시를 적용할 때 캐시 크기에 따른 실행시간 측정 프로그램을 작성하시오.

제한사항

• 캐시 교체 알고리즘은 LRU(Least Recently Used)를 사용한다.
• cache hit일 경우 실행시간은 1이다.
• cache miss일 경우 실행시간은 5이다.

나의 답안

function solution(cacheSize, cities) {
    if(cacheSize === 0) return cities.length * 5;
    
    let time = 0, cache = [];
    for(let i = 0; i < cities.length; i++) {
        if(cache.length < cacheSize) {
            if(cache.includes(cities[i].toLowerCase())) {
                time++;
                cache.splice(cache.indexOf(cities[i].toLowerCase()), 1);
                cache[cache.length] = cities[i].toLowerCase();
                continue;
            } else {
                cache.push(cities[i].toLowerCase());
                time += 5;
                continue;   
            }
        }
        
        if(cache.length >= cacheSize) {
            if(cache.includes(cities[i].toLowerCase())) {
                time++; 
                cache.splice(cache.indexOf(cities[i].toLowerCase()), 1);
                cache[cache.length] = cities[i].toLowerCase();
            } else {
                time += 5;
                cache.shift();
                cache.push(cities[i].toLowerCase())
            }
        }
    }
    return time;
}

접근 방식

• LRU : Least Recently Used
  1. 주로 캐시에서 메모리를 다루기 위해 사용된다.
  2. 가장 오랜 시간 사용되지 않은 페이지를 교체하는 운영체제의 페이지 교체 정책 알고리즘이다.
• 매개변수로 cacheSize, 즉 한번에 보관 가능한 data 수가 정해진다. 이때 새로 호출되는 data가 cache에 포함되어 있다면 cache hit이므로, 총 시간에 +1을 해주고, 해당 data가 다시 가장 최근에 사용된 data이므로 배열의 마지막 index로 이동해주면 된다.
• 반대로 새로 호출되는 data가 cache에 포함되어 있지 않은 경우에는 cache miss이므로, 총 시간에 +5를 해주고, 해당 data를 cahce 배열에 넣어주면 된다. 다만 cache는 cacheSize를 초과할 수 없기 때문에 push와 동시에 shift해주어 least recently used해서 인덱스 0 위치에 있는 data를 제거해주면 된다.
• cities에 포함되어 있는 도시명은 같은 도시명이어도 대문자, 소문자 차이가 있기 때문에 모든 도시명을 toLowerCase or toUpperCase해주어 통일시켜주면 된다.

Lv. 2: 2 x n 타일링✍️

---

문제 설명

가로 길이가 2이고 세로의 길이가 1인 직사각형모양의 타일이 있습니다. 이 직사각형 타일을 이용하여 세로의 길이가 2이고 가로의 길이가 n인 바닥을 가득 채우려고 합니다. 타일을 채울 때는 다음과 같이 2가지 방법이 있습니다.

타일을 가로로 배치 하는 경우
타일을 세로로 배치 하는 경우
예를들어서 n이 7인 직사각형은 다음과 같이 채울 수 있습니다.

제한사항

• 가로의 길이 n은 60,000이하의 자연수 입니다.
• 경우의 수가 많아 질 수 있으므로, 경우의 수를 1,000,000,007으로 나눈 나머지를 return해주세요.

나의 답안

function solution(n) {
    let initialArr = [1, 2];
    
    if(n < 2) return initialArr[n - 1];
    else for(let i = 2; i <= n; i++) {
        initialArr.push((initialArr[i - 1] + initialArr[i - 2]) % 1000000007);
    }
    return initialArr[n - 1];
}

접근 방식

• 타일의 크기는 오직 2 x 1이다. 사각형 안에 가로로 배치하면 2, 세로로 배치하면 1칸을 차지한다. 세로로 배치했을 때 두 개가 쌓이는 것은 문제와 아무 상관이 없다. 결국 경우의 수만 구하면 되기 때문에 이 문제는 피보나치 수 문제이다.
• 이전 피보나치 수 문제와 마찬가지로, 마지막 결과값만 % 1000000007 해주면 오답처리된다.