3.2프로그래머스 Lv.2 #11~20

개요

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

12. 구명보트

구명보트는 탐색(Greedy) 카테고리의 문제다.

그리디 알고리즘을 이 문제에 적용하면 가장 무거운 사람을 우선 태우고, 남는 무게가 있으면 가장 가벼운 사람을 태워보고 안되면 그냥 혼자 태우는 방식이다. 이게 가능한건 배의 최대 탑승인원이 2명이기 때문이다. 만약 2명 이상이라면 가벼운 사람 6명도 탈 수 있을테니 해당되지 않는다.

그리디 알고리즘을 적용하려면 우선 정렬을 해야한다. 이후 앞서 말한 식으로 문제에 적용한 알고리즘을 작성한다.

javascript
function solution(people, limit) {
    people.sort((a, b) => b - a);
    let left = 0, right = people.length - 1, boats = 0;
    while(left <= right){
        if(people[left] + people[right] <= limit){
            right--;
        }
        left++;
        boats++;
    }
    return boats;
}

13. 귤 고르기

귤 고르기는 수확한 귤을 크기별로 구분해서 넣어둔 배열 tangerine과, 여기서 뽑으려는 귤의 개수 k가 주어졌을 때, 최대한 크기의 종류가 다양하지 않게 귤을 뽑으면 몇 종류의 귤을 뽑을 수 있는지 구하는 함수를 작성하는 문제다.

나는 귤의 크기를 인덱스로 하여 같은 크기의 귤들을 세는 배열을 만들고, 그 배열의 숫자를 내림차순으로 정렬한 뒤 k에서 빼가며 종류의 수를 구했다.

javascript
function solution(k, tangerine) {
    const maxSize = Math.max(...tangerine);
    const grouped = Array.from({length: maxSize + 1}, () => 0);

    for(t of tangerine){
        grouped[t]++;
    }
    grouped.sort((a, b) => b - a);
    let types = 0;
    for(n of grouped){
        types++;
        if(k - n > 0) k -= n;
        else if(k - n <= 0) break;
    }
    return types;
}

13-1. 개선(리팩토링)

조건에 귤의 크기가 1부터 시작해 순차적으로 증가한다는 조건이 없으므로, 만약 가장 큰 귤이 100,000이고 딱 하나 들어있으면 정말 불필요하게 많은 배열을 만들게 된다. 따라서 Map이나 객체를 써서 실제 귤 크기만 카운트하는게 더 효율적이다.

javascript
const countMap = new Map();
for (const t of tangerine) {
  countMap.set(t, (countMap.get(t) || 0) + 1);
}
// 물론 정렬할땐 순서 정보가 담긴 배열을 써야한다.
const grouped = Array.from(countMap.values()).sort((a, b) => b - a);

또, for문을 정리할 수 있다. k - n > 0 조건은 어차피 k에 -n을 할 것이므로 사실상 필요가 없다.

javascript
function solution(k, tangerine) {
  const counts = new Map();
  for (const t of tangerine) {
    counts.set(t, (counts.get(t) || 0) + 1);
  }

  const sorted = Array.from(counts.values()).sort((a, b) => b - a);

  let types = 0;
  for (const c of sorted) {
    k -= c;
    types++;
    if (k <= 0) break;
  }

  return types;
}

14. N개의 최소공배수

N개의 최소공배수는 배열에 주어진 수들의 최소공배수를 구하는 문제로, 예전에 Lv.1 31번 문제에서 배운 유클리드 호제법을 활용해서 풀 수 있다.

즉, 어떤 두 수의 최소공배수는 두 수의 최대공약수로 서로 나눈 것들을 곱한 것에 최대공약수를 곱한 것이므로 arr을 순회하며 최소공배수들을 차근차근 구해나가면 된다.

javascript
function solution(arr) {
    function gcd(a, b){
        return b === 0 ? a : gcd(b, a % b);
    }
    
    function lcm(a, b){
        return (a * b) / gcd(a, b);
    }
    
    return arr.reduce((acc, cur) => acc = lcm(acc, cur) , 1)
}

16. 영어 끝말잇기

영어 끝말잇기는 참여자 수 n과 그들이 진행한 끝말잇기 정보가 담긴 배열 words가 주어지면 몇번째 참가자가 몇 라운드에서 떨어졌는지를 반환하는 함수를 작성하는 문제다.

나는 이미 나온 단어를 저장하는 배열과 이전에 나온 단어를 저장할 수 있는 prev, 떨어진 사람의 인덱스를 저장할 수 있는 loser라는 변수를 만들고, [0, 0]을 반환해야하는 상황인 notFinished라는 플래그를 만들어서 풀었다.

javascript
function solution(n, words) {
    let record = [words[0]];
    let prev = words[0];
    let loser = null;
    let notFinished = false;
    for(let i = 1; i < words.length; i++){
        const w = words[i]
        // 앞단어 끝 글자로 시작 안하면 탈락
        if(prev[prev.length - 1] !== w[0]){
            loser = i;
            break;
        }
        // 중복단어 말하면 탈락
       if(record.indexOf(w) !== -1){
           loser = i;
           break;
       }
        record.push(w);
        prev = w;
    }
    if(!loser) notFinished = true;
    loser = loser ? loser + 1 : 0
    const round = Math.ceil(loser / n);
    return [notFinished ? 0 : (loser % n === 0 ? n : loser % n), round]
}

16-1. Set으로 효율성 개선

indexOf()는 O(k)라 효율적이지 않다.(k = 단어의 수) 물론 제한 조건에서 words의 길이가 100이라 괜찮지만, Set이 이 상황에선 더 낫다.

javascript
const record = new Set([words[0]]);
if (record.has(w)) { ... }
record.add(w);

또, loser === null인지로 판단하는게 별도의 플래그를 만드는것보다 간결하고 가독성에도 더 도움이 된다. 또, prev를 굳이 저장하고 갱신하기보단 그냥 루프 안에서 확인하면 된다.

javascript
function solution(n, words) {
  const record = new Set();
  record.add(words[0]);

  for (let i = 1; i < words.length; i++) {
    const prev = words[i - 1];
    const cur = words[i];

    // 규칙 위반 체크
    if (prev[prev.length - 1] !== cur[0] || record.has(cur)) {
      const player = (i % n) + 1;
      const round = Math.floor(i / n) + 1;
      return [player, round];
    }
    record.add(cur);
  }

  return [0, 0];
}

17. 예상 대진표

예상 대진표는 토너먼트 시뮬레이션 문제로, 2의 지수인 참가자 수 n과 주인공 a, 라이벌 b의 번호가 주어지면 이 둘은 몇 라운드에서 만날 수 있는지를 구하는 함수를 작성하는 문제다.

각 라운드마다 1번은 2번과, 3번은 4번과...붙으며 참가자들의 번호는 라운드가 올라가면 절반으로 줄어든다(Math.ceil(현재 번호 / 2)).

a와 b를 매 라운드마다 갱신하며 몇번째 라운드에서 같은 번호가 되는지 확인하면 된다.

javascript
function solution(N, A, B) {
  let round = 0;

  while (A !== B) {
    A = Math.ceil(A / 2);
    B = Math.ceil(B / 2);
    round++;
  }

  return round;
}