[코딩테스트] 프로그래머스 javascript 2단계 - 스킬트리,행렬의 곱셈,n^2 배열 자르기,위장

스킬트리

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

프로그래머스

• 문제 설명

  선행 스킬이란 어떤 스킬을 배우기 전에 먼저 배워야 하는 스킬을 뜻합니다.

  예를 들어 선행 스킬 순서가 스파크 → 라이트닝 볼트 → 썬더일때, 썬더를 배우려면 먼저 라이트닝 볼트를 배워야 하고, 라이트닝 볼트를 배우려면 먼저 스파크를 배워야 합니다.

  위 순서에 없는 다른 스킬(힐링 등)은 순서에 상관없이 배울 수 있습니다. 따라서 스파크 → 힐링 → 라이트닝 볼트 → 썬더와 같은 스킬트리는 가능하지만, 썬더 → 스파크나 라이트닝 볼트 → 스파크 → 힐링 → 썬더와 같은 스킬트리는 불가능합니다.

  선행 스킬 순서 skill과 유저들이 만든 스킬트리1를 담은 배열 skill_trees가 매개변수로 주어질 때, 가능한 스킬트리 개수를 return 하는 solution 함수를 작성해주세요.

 

문제풀이

- 1. 이 문제는 index을 사용하여 문제를 풀면 된다.

- 2. 문자열 중 스킬에 포함되지 않은 것을 없애고 index를 찾으면 된다.

 

- 규칙 찾는 사고 방식을 키워야 한다.

 

- 참고로 정규식에서 변수를 사용하는 방법은 아래와 같다.

const reg = RegExp(`[${value}]`,'g')

 

function solution(skill, skill_trees) {
    let count = 0
    let reg = new RegExp(`[^${skill}]`,'g')
    for(let i = 0;i<skill_trees.length;i++){
        const arr = skill_trees[i].split(reg)
        console.log(arr)
        if (arr.join('')==='') count++
        else {
            if(skill.indexOf(arr.join(''))===0) count++
        }
    }
    
    return count
}

 

 

 

또는 이 방법처럼 정규식을 사용하지 않고 풀 수도 있다.

이때 arr.length가 0 인 경우를 생각해야 한다.

function solution(skill, skill_trees) {
    let count = 0
    
    for(let i=0;i<skill_trees.length;i++){
        const arr  = skill_trees[i].split('').filter(v=>skill.includes(v))
        if(arr.length===0) count++;
        else if (skill.indexOf(arr.join(''))===0) count++
        console.log(arr)
    }
    
    return count
}

 

행렬의 곱셈

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

프로그래머스

 

문제 설명

 2차원 행렬 arr1과 arr2를 입력받아, arr1에 arr2를 곱한 결과를 반환하는 함수, solution을 완성해주세요.

제한 조건

• 행렬 arr1, arr2의 행과 열의 길이는 2 이상 100 이하입니다.
• 행렬 arr1, arr2의 원소는 -10 이상 20 이하인 자연수입니다.
• 곱할 수 있는 배열만 주어집니다.

 

문제풀이

- 1. 행렬이 무엇인지 알아야 한다.

행렬이란 ? 

수 또는 다항식을 직사각형으로 배열 한 것이다. 

 행렬의 곱셈은 아래 사진 처럼 하나의 배열은 가로축으로 다른 하나는 세로축을 곱해 저장하는 것이다.

 

 

- 총 for문을 3번 돌려서 배열을 저장해야 한다.

- 이때 arr1과 arr2의 크기는 다를 수 있으니 변수 사용에 유의해야 한다.

 

- 행렬을 곱하기 위해서 row1 , col2, col1의 for문이 필요한다.

 

 

function solution(arr1, arr2) {
    const arr = []
    const [row1,col1] = [arr1.length, arr1[0].length]
    const [row2,col2] = [arr2.length, arr2[0].length]
    for (let i = 0;i<row1;i++){
       let cur = []
       let sum = 0
       for (let j = 0;j<col2;j++) {
           for (let k = 0; k<col1;k++){
               sum += arr1[i][k] * arr2[k][j]
           }
           cur.push(sum)
           sum=0
           // console.log(cur)
       }
        arr.push(cur)
      
    }
    return arr
}

 

코딩테스트를 잘하기 위해선 수학적 개념이 필요하다.

 

 

 

 

n^2 배열 자르기

 

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

프로그래머스

문제 설명

정수 n, left, right가 주어집니다. 다음 과정을 거쳐서 1차원 배열을 만들고자 합니다.

1. n행 n열 크기의 비어있는 2차원 배열을 만듭니다.
2. i = 1, 2, 3, ..., n에 대해서, 다음 과정을 반복합니다.
   • 1행 1열부터 i행 i열까지의 영역 내의 모든 빈 칸을 숫자 i로 채웁니다.
3. 1행, 2행, ..., n행을 잘라내어 모두 이어붙인 새로운 1차원 배열을 만듭니다.
4. 새로운 1차원 배열을 arr이라 할 때, arr[left], arr[left+1], ..., arr[right]만 남기고 나머지는 지웁니다.

정수 n, left, right가 매개변수로 주어집니다. 주어진 과정대로 만들어진 1차원 배열을 return 하도록 solution 함수를 완성해주세요.

 

문제풀이

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

- 2. 배열의 원소 값은 2차원 배열의 y와 x 축 중에 큰 값에서 +1 을 한 것과 같다.

 

행축은 Math.floor(현재값 / row )

열축은 현재값 / col 이다.

 

전체를 구할 필요 없이 구해야 하는 left~right까지만 구한다.

const solution = (n, left, right) => {
    const answer = [];
    
    for (let i=left; i <= right; i++) {
        const row = Math.floor(i/n);	// 행축(y)
        const col = i%n;	// 열축(x)
        answer.push(Math.max(row,col) + 1)
    }
    return answer;
}

 

위 문제는 알고리즘 사고력을 묻는 문제이다.

 

 

위장

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

프로그래머스

 

문제 설명

 

스파이들은 매일 다른 옷을 조합하여 입어 자신을 위장합니다.

예를 들어 스파이가 가진 옷이 아래와 같고 오늘 스파이가 동그란 안경, 긴 코트, 파란색 티셔츠를 입었다면 다음날은 청바지를 추가로 입거나 동그란 안경 대신 검정 선글라스를 착용하거나 해야 합니다.

종류이름

얼굴	동그란 안경, 검정 선글라스
상의	파란색 티셔츠
하의	청바지
겉옷	긴 코트

스파이가 가진 의상들이 담긴 2차원 배열 clothes가 주어질 때 서로 다른 옷의 조합의 수를 return 하도록 solution 함수를 작성해주세요.

 

문제풀이

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

- 1. 먼저 map을 사용해서 각각 패션 종류 별로 개수가 몇 개인지 저장한다. 

- 2. 만약 size가 1개라면 개수를 리턴한다.

- 3. 수학적 규칙을 파악한다.

3개가 된다면? (a+b+c) + (ab+bc+ca) + (abc)가지입니다.

어디서 많이 보시지 않았나요? 학창시절에 우리는 다항식을 배우는데 위의 가짓수는 n차식(n = 옷의 종류의 개수) 계수들의 합입니다.

즉 옷의 종류가 3가지고 각각의 옷의 개수가 a, b, c라면 (x+a)(x+b)(x+c) = x3 + (a+b+c)x2 + (ab+bc+ca)x + (abc)라는 식이 정립됩니다. 보이시죠? 총 조합의 개수가 계수에 다 포함되어 있습니다.

해당 식의 계수의 합을 구하려면 x=1을 대입해주면 됩니다. 그 후 맨 앞 x3 의 계수는 정답에 포함되지 않으므로 마지막에 1을 빼주는 겁니다.
x=1을 대입한 식은 (1+a)(1+b)(1+c)가 되고 그 값에 1을 뺀 후 리턴해주면 정답이 나오는 이유가 그것입니다.

 

즉, 옷 종류별로 (입었을 경우 + 안입었을 경우)를 곱하고 아무것도 입지 않은 경우를 제거한다.

 

function solution(clothes) {
    let count = new Map()
    clothes.forEach(v=>{
        count.set(v[1],(count.get(v[1])||0)+1)
    })
    console.log(count)
    if(count.size===1) return [...count][0][1]
    let min = [...count].reduce((pre,cur)=>{
        return pre*(cur[1]+1)
    },1)
    return min-1
    
}

 

위 문제는 수학적 규칙, 즉 경우의 수를 생각해서 풀어야 한다.