[코딩테스트] 프로그래머스 javascript 2단계 - 숫자의 표현,N개의 최소 공배수 ,점프와 순간이동,멀리뛰기,H-index,가장 큰 수

숫자의 표현

문제 설명

Finn은 요즘 수학공부에 빠져 있습니다. 수학 공부를 하던 Finn은 자연수 n을 연속한 자연수들로 표현 하는 방법이 여러개라는 사실을 알게 되었습니다. 예를들어 15는 다음과 같이 4가지로 표현 할 수 있습니다.

• 1 + 2 + 3 + 4 + 5 = 15
• 4 + 5 + 6 = 15
• 7 + 8 = 15
• 15 = 15

자연수 n이 매개변수로 주어질 때, 연속된 자연수들로 n을 표현하는 방법의 수를 return하는 solution를 완성해주세요.

 

 

문제풀이

- 이 문제는 규칙을 찾는 과정이 오래걸린다. 규칙은 홀수의 약수 개수를 구하면 된다.

 

이 문제는 수학적 규칙을 파악할 수 있는지를 물어보는 것이다.

 

function solution(n) {
    var answer = 0;
    for (let i=1;i<=n;i++){
        if(n%i===0&&i%2) answer++
    }
    return answer;
}

 

N개의 최소 공배수

https://school.programmers.co.kr/learn/courses/30/lessons/12953

프로그래머스

문제 설명

두 수의 최소공배수(Least Common Multiple)란 입력된 두 수의 배수 중 공통이 되는 가장 작은 숫자를 의미합니다. 예를 들어 2와 7의 최소공배수는 14가 됩니다. 정의를 확장해서, n개의 수의 최소공배수는 n 개의 수들의 배수 중 공통이 되는 가장 작은 숫자가 됩니다. n개의 숫자를 담은 배열 arr이 입력되었을 때 이 수들의 최소공배수를 반환하는 함수, solution을 완성해 주세요.

제한 사항

• arr은 길이 1이상, 15이하인 배열입니다.
• arr의 원소는 100 이하인 자연수입니다.

 

 

문제풀이

- 최소 공배수 함수를 생성한다.

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

- 배열 길이만큼 함수를 반복한다.

add.reduce((a,b)=>{return a*b / gcd(a,b)},1)

 

 곱하는 연산이 있으니 초기값 1로 설정 후 두 수를 곱하고 최소 공배수로 나눈 값을 저장한다,

 

 

전체 코드

function solution(arr) {
    return arr.reduce((pre,cur)=>{
        return pre*cur / gcd(pre,cur)
    },1)
    
    function gcd(a,b){
        return a%b?gcd(b,a%b):b
    }
}

 

 

점프와 순간이동

 

https://school.programmers.co.kr/learn/courses/30/lessons/12980

프로그래머스

문제 설명

OO 연구소는 한 번에 K 칸을 앞으로 점프하거나, (현재까지 온 거리) x 2 에 해당하는 위치로 순간이동을 할 수 있는 특수한 기능을 가진 아이언 슈트를 개발하여 판매하고 있습니다. 이 아이언 슈트는 건전지로 작동되는데, 순간이동을 하면 건전지 사용량이 줄지 않지만, 앞으로 K 칸을 점프하면 K 만큼의 건전지 사용량이 듭니다. 그러므로 아이언 슈트를 착용하고 이동할 때는 순간 이동을 하는 것이 더 효율적입니다. 아이언 슈트 구매자는 아이언 슈트를 착용하고 거리가 N 만큼 떨어져 있는 장소로 가려고 합니다. 단, 건전지 사용량을 줄이기 위해 점프로 이동하는 것은 최소로 하려고 합니다. 아이언 슈트 구매자가 이동하려는 거리 N이 주어졌을 때, 사용해야 하는 건전지 사용량의 최솟값을 return하는 solution 함수를 만들어 주세요.

예를 들어 거리가 5만큼 떨어져 있는 장소로 가려고 합니다.
아이언 슈트를 입고 거리가 5만큼 떨어져 있는 장소로 갈 수 있는 경우의 수는 여러 가지입니다.

• 처음 위치 0 에서 5 칸을 앞으로 점프하면 바로 도착하지만, 건전지 사용량이 5 만큼 듭니다.
• 처음 위치 0 에서 2 칸을 앞으로 점프한 다음 순간이동 하면 (현재까지 온 거리 : 2) x 2에 해당하는 위치로 이동할 수 있으므로 위치 4로 이동합니다. 이때 1 칸을 앞으로 점프하면 도착하므로 건전지 사용량이 3 만큼 듭니다.
• 처음 위치 0 에서 1 칸을 앞으로 점프한 다음 순간이동 하면 (현재까지 온 거리 : 1) x 2에 해당하는 위치로 이동할 수 있으므로 위치 2로 이동됩니다. 이때 다시 순간이동 하면 (현재까지 온 거리 : 2) x 2 만큼 이동할 수 있으므로 위치 4로 이동합니다. 이때 1 칸을 앞으로 점프하면 도착하므로 건전지 사용량이 2 만큼 듭니다.

위의 3가지 경우 거리가 5만큼 떨어져 있는 장소로 가기 위해서 3번째 경우가 건전지 사용량이 가장 적으므로 답은 2가 됩니다.

제한 사항

• 숫자 N: 1 이상 10억 이하의 자연수
• 숫자 K: 1 이상의 자연수

 

문제풀이

- 1. 이 문제는 규칙을 찾는 것이 중요하다.

- 2. 수를 2진수로 나누면 (2로 나누고 나머지 횟수를 세는 것과 같다) 0 즉 나머지가 나온 횟수와 같다.

 

function solution(n)
{
    var ans = 0;

    if (n===1) ans++
    ans = n.toString(2).replaceAll("0",'').length

    return ans;
}

 

위 문제는 아래처럼 풀 수도 있다.

function solution(n)
{
    let count = 0;
    while(n>0){
        if(n%2) {
            count++; n--
        } else{
            n/=2
        }
    }
    return count
}

 

 

멀리뛰기 - DP

https://school.programmers.co.kr/learn/courses/30/lessons/12914?language=javascript 

프로그래머스

 

 

문제 설명

효진이는 멀리 뛰기를 연습하고 있습니다. 효진이는 한번에 1칸, 또는 2칸을 뛸 수 있습니다.

칸이 총 4개 있을 때, 효진이는
(1칸, 1칸, 1칸, 1칸)
(1칸, 2칸, 1칸)
(1칸, 1칸, 2칸)
(2칸, 1칸, 1칸)
(2칸, 2칸)
의 5가지 방법으로 맨 끝 칸에 도달할 수 있습니다. 멀리뛰기에 사용될 칸의 수 n이 주어질 때, 효진이가 끝에 도달하는 방법이 몇 가지인지 알아내, 여기에 1234567를 나눈 나머지를 리턴하는 함수, solution을 완성하세요. 예를 들어 4가 입력된다면, 5를 return하면 됩니다.

 

문제풀이

- 이 문제는 DP(동적 프로그래밍) 문제이다.

 즉, 경우의 수가 많으니 규칙을 찾고 중복 연산을 줄여야 한다.

-  이 문제는 이전 2개의 값을 합치면 현재 값이 된다. (피보나치 수열과 비슷하다)

 

function solution(n) {
    var answer = 0;
    var dp=[];
    dp[1]=1;
    dp[2]=2;
    for(var i=3;i<=n;i++){
        dp[i]=(dp[i-1]+dp[i-2]) %1234567;
    }
    answer=dp[n];
    return answer
}

 

1234567로 나눠야 하는 것을 잊지말자!!

 

 

H-index

 

https://school.programmers.co.kr/learn/courses/30/lessons/42747

프로그래머스

문제 설명

H-Index는 과학자의 생산성과 영향력을 나타내는 지표입니다. 어느 과학자의 H-Index를 나타내는 값인 h를 구하려고 합니다. 위키백과1에 따르면, H-Index는 다음과 같이 구합니다.

어떤 과학자가 발표한 논문 n편 중, h번 이상 인용된 논문이 h편 이상이고 나머지 논문이 h번 이하 인용되었다면 h의 최댓값이 이 과학자의 H-Index입니다.

어떤 과학자가 발표한 논문의 인용 횟수를 담은 배열 citations가 매개변수로 주어질 때, 이 과학자의 H-Index를 return 하도록 solution 함수를 작성해주세요.

 

 

문제풀이

- 오름차순 정렬한 후 for문을 돌면서 i 이상의 개수, 이하의 개수를 센다.

- 그 중 가장 큰 값을 리턴한다.

function solution(citations) {
    let arr = citations.sort((a,b)=>a-b)
    let answer = []
    
    for(let i=0;i<=Math.max(...arr);i++){
        const more = arr.filter(v=>v>=i).length
        const less = arr.filter(v=>v<=i).length
        if(more>=i) answer.push(i);
        
    }
    
    
    
    return Math.max(...answer)      
}

 

굳이 arr 저장 후 Math.max 메서드 이용하지 않고 큰 수 부터 확인 후 리턴해도 된다.

function solution(citations) {
    citations.sort((a,b)=>a-b)
    for(let i=Math.max(...citations);i>=0;i--){
        const more = citations.filter(v=>v>=i).length
        const less = citations.filter(v=>v<=i).length
        if(more>=i) return i
    }
}

 

 

가장 큰 수

https://school.programmers.co.kr/learn/courses/30/lessons/42746

프로그래머스

 

문제 설명

0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요.

예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다.

0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요.

 

문제풀이

- 이 문제는 정렬문제이다.

- 문자열로 정렬하되 앞뒤를 합쳤을 때 기준으로 정렬하면 된다. 

-  이 문제는 이전 2개의 값을 합치면 현재 값이 된다. (피보나치 수열과 비슷하다)

 

function solution(numbers) {
    const test = numbers.map(v=>v.toString()).sort()
    console.log(test)
    let arr = numbers.map(v=>v.toString())
                    .sort((a,b)=>(b+a) - (a+b))    
    if(arr[0]==='0') return '0'
    return arr.join('')
    
    
}

 

'000'인 경우는 '0'인 것을 잊지말자!!

 

 

캐시

https://school.programmers.co.kr/learn/courses/30/lessons/17680

프로그래머스

 

문제 설명

캐시

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

어피치에게 시달리는 제이지를 도와, DB 캐시를 적용할 때 캐시 크기에 따른 실행시간 측정 프로그램을 작성하시오.

 

LRU 알고리즘 : 가장  오랫동안 참조되지 않은  페이지를 교체하는 기법

 

 

문제풀이

- 이 문제는 LRU 알고리즘을 알아야 한다. 즉 코딩테스트에서 CS 지식을 확인한다.

- 가장 오랫동안 참조되지 않은 데이터를 삭제해야 하기 때문에 캐시 hit 일 경우 최신 데이터로 배열 순서를 변경해야 한다.

 

배열 순서 변경을 하지 않아 오래 걸렸던 문제이다...

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

조건을 잊지말자!!