[코딩테스트] 프로그래머스 javascript 2단계 - 뉴스 클러스터링 ,연속 부분 수열 합의 개수,피로도,땅따먹기,방문 길이

뉴스 클러스터링

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

프로그래머스

문제 설명

 

유사한 기사를 묶는 기준을 정하기 위해서 논문과 자료를 조사하던 튜브는 "자카드 유사도"라는 방법을 찾아냈다.

자카드 유사도는 집합 간의 유사도를 검사하는 여러 방법 중의 하나로 알려져 있다. 두 집합 A, B 사이의 자카드 유사도 J(A, B)는 두 집합의 교집합 크기를 두 집합의 합집합 크기로 나눈 값으로 정의된다.

예를 들어 집합 A = {1, 2, 3}, 집합 B = {2, 3, 4}라고 할 때, 교집합 A ∩ B = {2, 3}, 합집합 A ∪ B = {1, 2, 3, 4}이 되므로, 집합 A, B 사이의 자카드 유사도 J(A, B) = 2/4 = 0.5가 된다. 집합 A와 집합 B가 모두 공집합일 경우에는 나눗셈이 정의되지 않으니 따로 J(A, B) = 1로 정의한다.

자카드 유사도는 원소의 중복을 허용하는 다중집합에 대해서 확장할 수 있다. 다중집합 A는 원소 "1"을 3개 가지고 있고, 다중집합 B는 원소 "1"을 5개 가지고 있다고 하자. 이 다중집합의 교집합 A ∩ B는 원소 "1"을 min(3, 5)인 3개, 합집합 A ∪ B는 원소 "1"을 max(3, 5)인 5개 가지게 된다. 다중집합 A = {1, 1, 2, 2, 3}, 다중집합 B = {1, 2, 2, 4, 5}라고 하면, 교집합 A ∩ B = {1, 2, 2}, 합집합 A ∪ B = {1, 1, 2, 2, 3, 4, 5}가 되므로, 자카드 유사도 J(A, B) = 3/7, 약 0.42가 된다.

이를 이용하여 문자열 사이의 유사도를 계산하는데 이용할 수 있다. 문자열 "FRANCE"와 "FRENCH"가 주어졌을 때, 이를 두 글자씩 끊어서 다중집합을 만들 수 있다. 각각 {FR, RA, AN, NC, CE}, {FR, RE, EN, NC, CH}가 되며, 교집합은 {FR, NC}, 합집합은 {FR, RA, AN, NC, CE, RE, EN, CH}가 되므로, 두 문자열 사이의 자카드 유사도 J("FRANCE", "FRENCH") = 2/8 = 0.25가 된다.

문제풀이

- 1.함수를 생성해서 알파벳만을 2개씩 자른 배열을 만든다.

  소문자로 변경 후 arr로 저장 

 

알파벳만을 고르는 방법
a. if (str >= "A" && str <= "Z")
b. str.match(/[A-Za-z]{2}/)

 

- 2. 교집합 확인과 합집합 확인한다.

 교집합은 set으로도 가능하다.

const set = new Set([...arr1, ...arr2]);

- 3. 유사도를 계산한다.

 

function solution(str1, str2) {
    //1. str에서 알파벳만을 골라서 배열에 저장한다. 
    let arr1 = erase(str1)
    let arr2 = erase(str2)
    //2. 교집합 확인하기
    const same = []
    const union = []
    for(let i=0;i<arr1.length;i++){
        if(arr2.includes(arr1[i])) {
            same.push(arr1[i])
            let j = arr2.indexOf(arr1[i])
            arr2.splice(j,1)
        }
        union.push(arr1[i])
    }
    for(let i=0;i<arr2.length;i++){
        union.push(arr2[i])
    }
    
    if(!union.length && !same.length) return 65536
    return Math.floor(same.length/union.length*65536)
    
}

function erase(str){
    let s = str.toLowerCase()
    const arr = []
    for(let i=0;i<s.length-1;i++) {
        if(s[i]>="a"&&s[i]<='z'&&s[i+1]>='a'&&s[i+1]<='z'){
            arr.push(s[i]+s[i+1])
        }
    }
    return arr
}

 

연속 부분 수열 합의 개수

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

프로그래머스

문제 설명

 

철호는 수열을 가지고 놀기 좋아합니다. 어느 날 철호는 어떤 자연수로 이루어진 원형 수열의 연속하는 부분 수열의 합으로 만들 수 있는 수가 모두 몇 가지인지 알아보고 싶어졌습니다. 원형 수열이란 일반적인 수열에서 처음과 끝이 연결된 형태의 수열을 말합니다. 예를 들어 수열 [7, 9, 1, 1, 4] 로 원형 수열을 만들면 다음과 같습니다.

원형 수열은 처음과 끝이 연결되어 끊기는 부분이 없기 때문에 연속하는 부분 수열도 일반적인 수열보다 많아집니다.
원형 수열의 모든 원소 elements가 순서대로 주어질 때, 원형 수열의 연속 부분 수열 합으로 만들 수 있는 수의 개수를 return 하도록 solution 함수를 완성해주세요.

문제풀이

- 1.합의 중복을 제거해야 하므로 set을 생성한다.

- 2. 연속 수열이므로 concat을 사용해 element를 이어 붙인다.

- 3. 더해가면서 계속 set에 넣는다. 

 

i는 0일 때 , j는 0~끝까지 돈다. 이과정을 원래 길이만큰 반복하면서 i+j의 합을 더해준다.

 

function solution(elements) {
    const set = new Set()
    const arr = elements.concat(elements)
    
    for(let i=0;i<elements.length;i++){
        let sum = 0;
        for(let j=0;j<elements.length;j++){
            sum+= arr[i+j]
            console.log(sum)
            set.add(sum)
        }
    }
    
    return set.size
}

 

피로도

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

프로그래머스

문제 설명

XX게임에는 피로도 시스템(0 이상의 정수로 표현합니다)이 있으며, 일정 피로도를 사용해서 던전을 탐험할 수 있습니다. 이때, 각 던전마다 탐험을 시작하기 위해 필요한 "최소 필요 피로도"와 던전 탐험을 마쳤을 때 소모되는 "소모 피로도"가 있습니다. "최소 필요 피로도"는 해당 던전을 탐험하기 위해 가지고 있어야 하는 최소한의 피로도를 나타내며, "소모 피로도"는 던전을 탐험한 후 소모되는 피로도를 나타냅니다. 예를 들어 "최소 필요 피로도"가 80, "소모 피로도"가 20인 던전을 탐험하기 위해서는 유저의 현재 남은 피로도는 80 이상 이어야 하며, 던전을 탐험한 후에는 피로도 20이 소모됩니다.

이 게임에는 하루에 한 번씩 탐험할 수 있는 던전이 여러개 있는데, 한 유저가 오늘 이 던전들을 최대한 많이 탐험하려 합니다. 유저의 현재 피로도 k와 각 던전별 "최소 필요 피로도", "소모 피로도"가 담긴 2차원 배열 dungeons 가 매개변수로 주어질 때, 유저가 탐험할수 있는 최대 던전 수를 return 하도록 solution 함수를 완성해주세요.

제한사항

• k는 1 이상 5,000 이하인 자연수입니다.

 

문제풀이

- 1.완전탐색, 즉 모든 경우의 수를 확인할 수 있ㅇ르 정도로 배열의 길이가 짧다.

- 2. DFS로 시작점을 다르게 설정해서 모든 경우를 확인한다. 

- 3. count를 Math.max로 반복해서 초기화한다.

 

function solution(k, dungeons) {
    let answer = 0
    let visit = dungeons.map(v=>false)
    DFS(0,k)
    
    function DFS(count,f){
        answer = Math.max(answer,count)
        
        for(let i = 0;i<dungeons.length;i++){
            const [need,sub] = dungeons[i]
            if(!visit[i] && f>=need){
                visit[i]=true
                DFS(count+1,f-sub)
                visit[i]=false
            }
        }
    }
    
    
    return answer
}

 

땅따먹기

 

프로그래머스

 

문제 설명

땅따먹기 게임을 하려고 합니다. 땅따먹기 게임의 땅(land)은 총 N행 4열로 이루어져 있고, 모든 칸에는 점수가 쓰여 있습니다. 1행부터 땅을 밟으며 한 행씩 내려올 때, 각 행의 4칸 중 한 칸만 밟으면서 내려와야 합니다. 단, 땅따먹기 게임에는 한 행씩 내려올 때, 같은 열을 연속해서 밟을 수 없는 특수 규칙이 있습니다.

예를 들면,

| 1 | 2 | 3 | 5 |

| 5 | 6 | 7 | 8 |

| 4 | 3 | 2 | 1 |

로 땅이 주어졌다면, 1행에서 네번째 칸 (5)를 밟았으면, 2행의 네번째 칸 (8)은 밟을 수 없습니다.

마지막 행까지 모두 내려왔을 때, 얻을 수 있는 점수의 최대값을 return하는 solution 함수를 완성해 주세요. 위 예의 경우, 1행의 네번째 칸 (5), 2행의 세번째 칸 (7), 3행의 첫번째 칸 (4) 땅을 밟아 16점이 최고점이 되므로 16을 return 하면 됩니다.

 

문제풀이

- 이 문제는 DP, 즉 동적 프로그래밍 문제이다. 경우의 수가 많고 중복되는 연산이 많으므로 연산의 수를 줄여야 한다.

아래 영상을 반복 청취하길 바란다. 

 

- 1. 한 줄씩 건너기 위해서 모든 경우의 수를 확인하고 가장 큰 값으로 리턴한다. 

- 2. 가장 마지막 배열에서 최댓값을 리턴한다.

function solution(land) {
    let arr = land.map(v=>v.map(a=>0))
    arr[0] = land[0]
    // console.log(arr)
    
    const col = 4;
    for(let i = 1;i<land.length;i++){
        for(let j = 0;j<col;j++){
            for(let k =0;k<col;k++){
                if(j!==k){
                    // console.log('('+i+','+j+')  k :' +k)
                    let sum = land[i][j] + arr[i-1][k]
                    arr[i][j] = Math.max(arr[i][j],sum)
                    // console.log(arr)
                }
            }
        }
    }
    return Math.max(...arr[arr.length-1])
}

 

방문 길이

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

프로그래머스

문제 설명

게임 캐릭터를 4가지 명령어를 통해 움직이려 합니다. 명령어는 다음과 같습니다.

• U: 위쪽으로 한 칸 가기
• D: 아래쪽으로 한 칸 가기
• R: 오른쪽으로 한 칸 가기
• L: 왼쪽으로 한 칸 가기

캐릭터는 좌표평면의 (0, 0) 위치에서 시작합니다. 좌표평면의 경계는 왼쪽 위(-5, 5), 왼쪽 아래(-5, -5), 오른쪽 위(5, 5), 오른쪽 아래(5, -5)로 이루어져 있습니다.

예를 들어, "ULURRDLLU"로 명령했다면

• 1번 명령어부터 7번 명령어까지 다음과 같이 움직입니다.

• 8번 명령어부터 9번 명령어까지 다음과 같이 움직입니다.

이때, 우리는 게임 캐릭터가 지나간 길 중 캐릭터가 처음 걸어본 길의 길이를 구하려고 합니다. 예를 들어 위의 예시에서 게임 캐릭터가 움직인 길이는 9이지만, 캐릭터가 처음 걸어본 길의 길이는 7이 됩니다. (8, 9번 명령어에서 움직인 길은 2, 3번 명령어에서 이미 거쳐 간 길입니다)

단, 좌표평면의 경계를 넘어가는 명령어는 무시합니다.

예를 들어, "LULLLLLLU"로 명령했다면

• 1번 명령어부터 6번 명령어대로 움직인 후, 7, 8번 명령어는 무시합니다. 다시 9번 명령어대로 움직입니다.

이때 캐릭터가 처음 걸어본 길의 길이는 7이 됩니다.

명령어가 매개변수 dirs로 주어질 때, 게임 캐릭터가 처음 걸어본 길의 길이를 구하여 return 하는 solution 함수를 완성해 주세요.

 

문제풀이

- 1. 방향 객체를 생성해서 [y축,x축] 을 저장한다.

- 2. 방문 기록이 겹치면 안되기 때문에 set에 저장한다.

     이때 출발점과 도착점 = 도착점과 출발점은 같은 것이므로 유의한다.

- 3. 방향을 움직이면서 출발점도착점 + 도착점출발점을 set에 저장한다.

- 4. set의 사이즈/ 2 를 해준다. (한 길 당 2개씩 저장했기 때문

function solution(dirs) {
    let [y,x] = [0,0]
    let visit = new Set()
    let dir = {U:[-1,0], D:[1,0], L:[0,-1],R:[0,1] }
    
    for (let s of dirs) {
        let d = dir[s]
        // console.log(d)
        const [ny,nx] =[ y+ d[0], x +d[1] ]
        if (ny>=-5&&ny<=5&&nx>=-5&&nx<=5) {
            visit.add(''+y +x +ny+nx)
            visit.add(''+ny+nx+y + x)
            y= ny;x = nx;
            // console.log(y,x)
        }
        
    }
    return visit.size/2
}