[프로그래머스] 09/14 문제 풀이

1. 전체 푼 문제

• lv2 : 멀리뛰기(12분)
• lv3 : 최고의 집합(9분)
• lv2 : N개의 최소공배수(18분)
• lv2 : 예상대진표(20분)
• lv2 : 점프와 순간이동(9분)
• lv2 : [1차] 캐시(1차:실패 / 2차:19분)

2. 명심할 것

2-1. 최대공약수 구하는 공식

function gcd(a, b) {
  return a % b ? gcd(b, a%b) : b
}

2-2. 누적은 'reduce()'

2-3. 원소 삭제는 'splice()'

반환을 삭제한 원소로 한다.

3. 주요 문제 풀이

3-1. N개의 최소공배수(링크)

- 풀이방법

이 문제의 핵심은 두 가지였다.

1. 각 배열의 원소가 몇 개이든 처음 두 원소의 최소공배수를 구하고,
   그 최소공배수와 다음 원소 간의 최소공배수를 구하는 식으로 하면
   N개의 최소공배수를 구할 수 있다.
   -> 최소공배수를 텍스트누적시킨다.
   -> 누적일 때 reduce()를 쓴다.

2. 최소공배수 공식
   -> 최대공약수 구하는 공식을 알면 '유클리드 호제법'으로 최소공배수도 구할 수 있다.

[결론] reduce()와 최대공약수 공식 알면 푼다.

- 기존 코드

function solution(arr) {
    var answer = 0;
    function getGcd(a,b){
        if(a<b){
            [b,a] = [a,b]
        }
        
        if(a%b === 0){
            return b
        }
        
        let gcd = 1;
        for(let i = 2; i <= b ; i++){
            if(a%i === 0 && b%i === 0){
                gcd = i
            }
        }
        return gcd
    }
    
    let lcm =  (arr[0] * arr[1]) / getGcd(arr[0], arr[1])
    
    if(arr.length > 2){
        for(let i = 2; i < arr.length; i++){
          lcm = (lcm * arr[i]) / getGcd(lcm, arr[i])
        }
    }
    else{
        return lcm
    }
    answer = lcm
    return answer;
}

- 개선 코드

function solution(arr) {
    var answer = 0;
    
    function getGcd(a,b){
        return a%b ? getGcd(b,a%b) :b 
    }
    
    answer = arr.reduce((a,b)=> {
        return a*b / getGcd(a,b)
    })
    return answer;
}

4. [1차]캐시 (링크)

풀이방법

LRU 알고리즘을 알고 있으면 충분히 풀 수 있는 문제였다.
하지만 나의 경우 cacheSize가 0일 때 예외처리를 안했고 끝까지 찾지 못해 첫번째는 실패를 했다.

기존코드

function solution(cacheSize, cities) {
    var answer = 0;
    let cache = []
    cities.map(city => {
        city = city.toLowerCase()
        if(cache.includes(city)){
            answer +=1
            cache = [...cache.slice(0,cache.indexOf(city)), ...cache.slice(cache.indexOf(city)+1)]
            cache.push(city)   
        }
        else{
            answer += 5
            if(cache.length < cacheSize){
                cache.push(city)
            }
            
            else if(cache.length === cacheSize && cacheSize!==0){
                cache = cache.slice(1)
                cache.push(city)
            }
        }
        // console.log(cache)
    })
    return answer;
}

개선코드

배열에서 한 원소를 remove하는 방식을 여태까지 slice()를 이용해 왔다. 하지만 이번 개선코드에서는 splice()를 사용해본다.

*splice()는 반환함수인데, 삭제한 원소를 반환한다.

cache = [...cache.slice(0,cache.indexOf(city)), ...cache.slice(cache.indexOf(city)+1)]

=>

cache.splice(cache.indexOf(city),1)