3.3프로그래머스 Lv.2 #21~30

개요

프로그래머스에 자바스크립트로 풀 수 있는 Lv.2 문제는 총 113문제가 있다. 정답률 높은 문제 순, 21 ~ 30번 문제 풀이 중 배울 점이 있는 풀이들 또는 고심해서 푼 문제들에서 기억하고 싶은 개념들을 완전히 내 것으로 만들고자 정리해본다.

21. n^2 배열 자르기

n^2 배열 자르기는 문제에서 시킨 그대로를 따라하는 코드가 아니라 본질을 이해하는것이 중요하다는 가르침을 주는 문제다.

문제는 이렇게 되어 있다:

• n, left, right가 주어지면 n행 n열의 2차원 배열을 만든다.
• 1행 1열부터 i행 i열까지 모든 숫자를 i로 채운다.
• 이 배열들을 모두 합친 하나의 배열을 만들고, arr라고 하면 arr[left] 부터 arr[right]까지 원소를 담은 배열을 반환하라.

하지만 제한 사항이 n을 무려 10^7까지 통과시켜야하기 때문에 배열을 곧이곧대로 만들면 바로 시간초과다. 이 문제는 그냥 arr[left]와 arr[right]의 수를 구하고 사이를 채우는 문제다.

예시를 통해 어떻게 답이 나올지 생각해보면, arr[i][j]는 i와 j 중 큰 수 + 1로 채워져 있다. 따라서 이것을 이용한다.

javascript
function solution(n, left, right) {
    const result = [];
    for(let i = left; i <= right; i++){
        const row = Math.floor(i / n);
        const col = i % n;
        result.push(Math.max(row, col) + 1);
    }
    return result;
}

22. 행렬의 곱셈

행렬의 곱셈은 두 행렬을 받아 행렬의 곱셈을 수행하는 함수를 작성하는 문제다.

앞에 있는 행렬의 행 수가 뒤에 있는 행렬의 열 수와 같아야 하고, 결과 행렬은 앞에 있는 행 수와 뒤에 있는 행렬의 열 수를 가지므로 이를 이용한 3중 for문으로 풀었다.

javascript
function solution(arr1, arr2) {
    const m = arr1.length;
    const k = arr1[0].length;
    const n = arr2[0].length;
    const answer = Array.from({length: m}, () => Array(n).fill(0));
    for(let i = 0; i < m; i++){
        for(let j = 0; j < n; j++){
            for(let x = 0; x < k; x++){
                answer[i][j] += arr1[i][x] * arr2[x][j]
            }
        }
    }  
    return answer;
}

22-1. map과 reduce를 이용한 한줄 풀이

다소 직관적이진 않지만 중첩 for문이 없고 한 줄로 끝나는 간결한 코드가 있어서 가져왔다. 이 코드는 아래와 같이 작동한다:

• arr1.map((row) => ...) : arr1의 각 행으로 결과 행렬의 행들을 만든다.
• arr2[0].map((x, y) => ...) : arr2의 열 개수만큼 루프한다.
• row.reduce((acc, num, idx) => ..., 0) : row의 각 원소(num)와 인덱스를 사용해서 arr1의 (i, idx)와 arr2의 (idx, y)를 곱한 후 합산한다.

javascript
function solution(arr1, arr2) {
  return arr1.map((row) => 
    arr2[0].map((x, y) => 
      row.reduce((acc, num, idx) => acc + num * arr2[idx][y], 0)
    )
  )
}

23. H-Index

H-Index는 실제로 있는 지표를 바탕으로 하는 문제로, 어떤 과학자가 발표한 논문 중 h번 이상 인용된 논문이 h편 이상이고 나머지 논문은 h편 이하로 인용되었다면 h의 최댓값을 H-Index라고 할 때, 논문 인용 횟수를 담은 배열이 주어지면 H-Index를 반환하는 함수를 작성하는 문제다.

나는 정렬 후 인덱스로 인용 횟수를 비교하는 방식으로 문제를 풀었다.

javascript
function solution(citations) {
    citations.sort((a, b) => b - a);
    let h = 0;
    for(let i = 0; i < citations.length; i++){
        if(citations[i] >= i + 1){
            h = i + 1;
        } else{
            break;
        }     
    }
    return h;
}

23-1. while문 풀이

기본적인 아이디어는 동일하지만, while로 좀 더 간결하게 쓸 수 있다. i번째 논문의 인용 수가 i + 1보다 크거나 같으면 계속 진행하고 멈출때 i를 반환하면 된다.

javascript
function solution(citations) {
  citations.sort((a, b) => b - a);
  let i = 0;
  while (i + 1 <= citations[i]) i++;
  return i;
}

25. 기능개발

기능개발은 작업별 진척도를 담은 progresses라는 배열과 각각의 진척 속도를 담은 speeds라는 배열이 주어진다. 앞선 인덱스의 작업이 배포상 더 우선순위가 되어야 하기 때문에 뒷 인덱스의 작업이 끝나도 배포는 앞선 것이 될때 같이 해야한다고 하면, 각 배포마다 몇 개의 기능이 배포되는지 반환하는 함수를 작성하는 문제다.

나는 우선 progresses가 며칠이 지나야 끝나는지를 계산하고, 해당 일수들의 배열을 순회하며 배포일별로 묶었다.

javascript
function solution(progresses, speeds) {
    const remDays = progresses.map((v, i) => {
        return Math.ceil((100 - v) / speeds[i]);
    });
    const answer = [];
    let current = remDays[0];
    let count = 1;
    for(let i = 1; i < remDays.length; i++){
        if(current >= remDays[i]){
            count++;
        } else {
            answer.push(count);
            count = 1;
            current = remDays[i]
        }
    }
    answer.push(count);
    
    return answer;
}

26. 피로도

피로도는 현재 체력과, 던전들마다 입장하기 위한 최소 체력 조건 및 소요 체력이 중첩 배열 형태로 주어지면 최대 몇 개의 던전을 돌 수 있는지 구하는 함수를 작성하는 문제다.

나는 DFS(재귀)로 풀었다. 즉,

• 우선 바깥에 최대값을 저장하는 max라는 변수와 방문여부를 표시할 visited라는 배열을 만들었다.
• dfs 헬퍼 함수는 체력과 카운트를 받아 재귀적으로 실행된다.
  • 던전을 순회하는데, i번째 던전을 방문하기 전이고 최소 체력보다 현재 체력이 많으면 해당 던전을 방문한 것으로 표시한다. 체력을 깎고 카운트를 늘려 dfs를 실행한다.
  • dfs를 실행한 이후에는 방문 여부를 다시 false로 표시해서 백트래킹한다.

javascript
function solution(k, dungeons) {
    let max = 0;
    const n = dungeons.length;
    const visited = Array(n).fill(false);
    
    function dfs(health, count){
        max = Math.max(max, count);
        for(let i = 0; i < n; i++){
            const [minBar, cost] = dungeons[i];
            if(!visited[i] && health >= minBar){
                visited[i] = true;
                dfs(health - cost, count + 1);
                visited[i] = false; // 백트래킹(원복)
            }
        }
    }
    dfs(k, 0);
    return max;
}

27. 캐시

캐시는 캐시 크기 cacheSize와 도시이름 배열 cities를 받고, 캐시 교체 알고리즘으로 LRU(Last Recently Used)를 쓸 때, cache에 있으면 실행시간 1, 없으면 5인 상황에서 cities의 모든 도시들을 찾을때 총 실행시간을 구하는 함수를 작성하는 문제다.

나는 cache라는 배열을 만들고, cities를 순회하며 캐시에 추가하며 캐시에 없다면 시간에 5 추가하고 캐시를 교체, 있다면 시간에 1을 추가하고 원래 있던 해당 city를 제거하고 맨 끝에 다시 붙여 캐시를 업데이트했다.

javascript
function solution(cacheSize, cities) {
    if(cacheSize === 0) return cities.length * 5;
    let cache = [];
    let time = 0;
    for(let i = 0; i < cities.length; i++){
        const city = cities[i].toLowerCase();
        // 캐시에 없을때 : 5 추가하고 캐시 교체
        if(cache.indexOf(city) === -1){
            time += 5;
            if(cache.length === cacheSize){
                cache.shift();    
            }
            cache.push(city);
        } else {
            // 캐시에 있을때 : 1추가하고 캐시 교체
            time++;
            cache = cache.filter((_, i) => i !== cache.indexOf(city));
            cache.push(city)
        }
    }
    return time;
}

27-1. 개선

우선 indexOf를 두 번 호출하는데, 맨 위에 한 번 변수로 할당하고 계속 쓰는게 낫다.

또, filter를 써서 해당 원소를 제거하는데 filter는 배열 전체를 새로 만들어 반환하기에 splice(idx, 1)을 쓰는게 원소만 제거하기엔 더 낫다.

javascript
function solution(cacheSize, cities) {
  if (cacheSize === 0) return cities.length * 5;

  let cache = [];
  let time = 0;

  for (let city of cities) {
    city = city.toLowerCase();
    const idx = cache.indexOf(city); // 중복 호출 방지

    if (idx === -1) {
      time += 5;
      if (cache.length === cacheSize) cache.shift();
      cache.push(city);
    } else {
      time += 1;
      cache.splice(idx, 1); // 해당 원소 제거
      cache.push(city);
    }
  }

  return time;
}

28. 튜플

튜플은 중복되는 원소가 없는 튜플을 표현하는 집합이 담긴 문자열 s가 주어질 때 s가 표현하는 튜플을 배열에 담아 반환하는 함수를 작성하는 문제다.

예를 들어, s가 "{{1,2,3},{2,1},{1,2,4,3},{2}}"라면 {} 안에서 순서는 상관없으나 1개일때는 2만, 2개일때는 2, 1만... 있다는 점을 활용해 실제 튜플은 [2, 1, 3, 4]였음을 알 수 있다.

나는 우선 문자열을 파싱해 s를 중첩 배열 형태로 만들었다. 이후, 배열의 길이 순서대로 정렬하고 배열들을 순회하며 원소들을 추가했다.

javascript
function solution(s) {
    const arr = s.slice(2, -2).split('},{').map(str => str.split(',').map(Number));
    arr.sort((a, b) => a.length - b.length);
    const answer = [];
    for(const set of arr){
        for(const num of set){
            if(answer.indexOf(num) === -1){
                answer.push(num);
            }
        }
    }
    return answer;
};

28-1. 정규표현식과 set, reduce를 쓴 풀이

정규표현식으로 문자를 파싱하고, reduce로 중첩 배열을 만든 후 set에 값을 추가하고 이걸 배열로 바꾸어 반환한 답이 있었다. 정규표현식에 팀원들이 익숙하다면, 또 reduce를 쓴다면 아무래도 중첩 for문 보다는 좀 더 간결한 표현이 될것이라고 생각한다.

javascript
const solution = s => tuple(changeMatrix(getSets(s)));

const getSets = s => {
  const sets = s.match(/{[\d,]+}/g); // {…} 패턴만 추출
  return sets
    .map(set => set.match(/[\d]+,?/g).map(v => parseInt(v))) // 숫자 배열로 변환
    .sort((a, b) => a.length - b.length); // 길이순 정렬
};

const changeMatrix = sets => sets.reduce((_, set) => _.concat(set), []);

const tuple = arr => [
  ...arr.reduce((set, value) => set.add(value), new Set())
];

30. 프로세스

프로세스는 운영체제가 프로세스를 우선순위를 가진 큐로 관리할때, 몇번째로 실행되는지 알고 싶은 프로세스의 위치 location과 프로세스의 중요도가 프로세스 순서대로 담긴 배열 priorities가 주어지면 해당 프로세스가 몇번째로 실행되는지 반환하는 함수를 작성하는 문제다.

위치 정보를 저장해야하므로 값(우선순위)과 인덱스를 저장한 배열을 큐로 만들고, 하나씩 빼며(shift) 만약 우선순위가 더 높은게 있으면 해당 큐를 뒤로 미루는(push) 로직을 만들었다.

javascript
function solution(priorities, location) {
    let queue = priorities.map((v, i) => [v, i]);
    let count = 0;
    
    while(queue.length){
        for(const q of queue){
            let [priority, idx] = queue.shift();
            if(queue.some(([p])=> p > priority)){
                queue.push([priority, idx]);
            } else{
                count++;
                if(idx === location) return count;
            }
        }
    }
}