2.3프로그래머스 Lv.1 #41~50

개요

프로그래머스에 자바스크립트로 풀 수 있는 Lv.1 문제는 총 82문제가 있다. 정답률 높은 문제 순, 41 ~ 50번 문제 풀이 중 배울 점이 있는 풀이들에서 배운 개념들을 내 것으로 만들고자 정리해본다.

42. 숫자 문자열과 영단어

이 문제는 숫자의 일부 자릿수를 영단어로 바꾸는 암호를 받으면 다시 원래 숫자로 되돌리는 함수를 작성하는 문제다. 예를 들어 1478 → "one4seveneight"가 되므로 후자를 받으면 전자를 반환해야 한다.

나는 처음에 이렇게 풀었는데, 테스트 케이스 7~10번을 통과하지 못했다.

javascript
function solution(s) {
    let answer = ""
    let temp = ""
    for(let i = 0; i < s.length; i++){
        if(Number(s[i])) {
            answer += s[i];
            continue;
        }
        temp += s[i]
        if(dictionary[temp]){
            answer += dictionary[temp];
            temp = "";
        } 
    }
    return Number(answer);
}

const dictionary = {
    "zero" : 0,
    "one" : 1,
    "two" : 2,
    "three" : 3,
    "four" : 4,
    "five" : 5,
    "six" : 6,
    "seven" : 7,
    "eight" : 8,
    "nine" : 9,
}

왜 그런지 한참 고민했는데, 0이 falsy value이기 때문에 if(Number(s[i]))에서 0이 나와 false를 반환하고, 마찬가지로 값을 숫자로 지정해둔 dictionary 때문에 if(dictionary[temp]) 또한 zero일때 false를 반환했기 때문이었다.

이걸 깨닫고 이렇게 수정해 풀었다. dictionary의 값들을 어차피 string으로 합치고 맨 마지막에 Number로 바꾸기 때문에 다 string으로 만들었고(이건 사실 처음부터 그랬어야 했다. Typescript 상황이라고 생각해보라!), s[i]가 "0" 일때도 조건문에 포함했다.

javascript
function solution(s) {
    let answer = ""
    let temp = ""
    for(let i = 0; i < s.length; i++){
        if(s[i] === "0"){
            answer += "0";
            continue;
        }
        if(Number(s[i])) {
            answer += s[i];
            continue;
        }
        temp += s[i]
        if(dictionary[temp]){
            answer += dictionary[temp];
            temp = "";
        } 
    }
    return Number(answer);
}

const dictionary = {
    "zero" : "0",
    "one" : "1",
    "two" : "2",
    "three" : "3",
    "four" : "4",
    "five" : "5",
    "six" : "6",
    "seven" : "7",
    "eight" : "8",
    "nine" : "9",
}

0일때와 Number일때를 나눠서 처리했지만, 사실 if(!isNaN(s[i]))로 한번에 처리가 가능하다. 즉, if(Number(s[i]))에서는 0이 falsy value이기 때문에 따로 처리해야하지만, isNaN을 이용하면 0은 0 자체로 falsy하긴 하지만 숫자긴 하기 때문에 이 조건문으로 한번에 처리된다.

또, dictionary를 굳이 함수 밖에 정의할 필요는 없다. 외부 의존도를 줄이기 위해 함수 안에 적는 것도 괜찮다.

42-1. Object.entries

javascript
function solution(s) {
    const dict = {
        zero: "0",
        one: "1",
        two: "2",
        three: "3",
        four: "4",
        five: "5",
        six: "6",
        seven: "7",
        eight: "8",
        nine: "9"
    };

    for (let [word, digit] of Object.entries(dict)) {
        s = s.replaceAll(word, digit);
    }

    return Number(s);
}

ES2021 이상에서 지원하는 replaceAll로 한번에 처리하는것도 가능하다.

42-2. split과 join

split과 join을 활용하여 해결할 수도 있다. 숫자는 인덱스라는 좋은 키가 이미 있으므로, 배열을 써도 좋은 사전을 만들 수 있다.

아래 풀이에선 numbers라는 변수에 모든 영단어를 넣어두고, 받은 문자열을 numbers의 영단어 각각을 기준으로 split하고 인덱스를 사이에 넣는 방식으로 합쳐서 답을 반환한다.

javascript
function solution(s) {
  const numbers = ["zero","one","two","three","four","five","six","seven","eight","nine"];
  numbers.forEach((word, i) => s = s.split(word).join(i));
  return Number(s);
}

44. 콜라 문제

콜라 문제는 콜라 a병을 가져다주면 b병을 새로 준다고 하면, n병일때 총 몇 병을 새로 받아서 먹을 수 있냐는 문제다.

나는 재귀가 생각나서 재귀형태로 풀었지만, n이 100만 이하의 자연수까지를 통과해야했고 재귀로 풀 경우 스택 오버플로가 일어났다.

javascript
function solution(a, b, n) {
  if (n < a) return 0; 
  const exchanged = Math.floor(n / a) * b;
  return exchanged + solution(a, b, exchanged + (n % a));
}

44-1. 반복문으로 풀기

따라서 이 경우 반복문으로 푸는 것이 안전하다.

javascript
function solution(a, b, n){
    let total = 0;
    while(n >= a){
        const exchanged = Math.floor(n / a) * b;
        total += exchanged;
        n = exchanged + (n % a);
    }
    return total;
}

for문으로 이렇게 푼 분도 있다:

javascript
function solution(a, b, n) {
    let answer = 0;
    for(let i=a; i<=n; i+=a) {
        answer += b;
        n += b;
    }
    return answer;
}

44-2. 수학적 풀이

a를 주고 b를 돌려받는다는 것은 한번 교환하면 a - b만큼 없어지는 것이라 볼 수 있다. 따라서 n/(a-b)를 계속 해서 몇번째에 n이 0이 되는지 보면 된다.

교환을 총 x번 한다면 최종 빈 병은 n - x(a - b)이고, 더 이상 교환하지 못하려면 < a여야 하므로, n - x(a - b) < a, 즉 x <= (n - b)/(a - b)이고, 가능한 최대 교환 수는 (n - b)/(a - b)이고 받는 콜라 수는 x * b이다.

javascript
// a개 주면 b병 받음, 시작 빈병 n개일 때 총 받는 콜라 수
const solution = (a, b, n) => Math.floor((n - b) / (a - b)) * b;

45. 문자열 내 마음대로 정렬하기

이 문제는 문자열이 담긴 배열 strings에서, 인덱스 넘버 n이 주어지면 해당 인덱스의 문자를 토대로 strings에 있는 문자열들을 정렬하는 문제다. 만약 해당 인덱스의 문자가 같다면, 문자열 전체를 보고 사전순으로 앞선 문자열을 앞에 배치한다.

두 가지 정렬 조건이 필요한데, 주어진 인덱스의 문자를 비교했을 때 같으면 문자열 전체를 사전순으로, 아니면 해당 문자를 비교한다. 나는 이렇게 풀었다. localeCompare과 charCodeAt()을 사용한 풀이다.

javascript
function solution(strings, n) {
    return strings.sort((a, b) => {
        if(a[n] === b[n]) return a.localeCompare(b);
        return a[n].charCodeAt() - b[n].charCodeAt();
    });
}

45-1. charCodeAt은 필요 없다.

사실 굳이 charCodeAt을 쓸 필요가 없다. 문자끼리의 대소 비교는 a[n] < b[n] 식으로 가능하고, 여기선 localeCompare를 일관적으로 쓰는게 가독성에 더 도움이 된다.

javascript
function solution(strings, n) {
    return strings.sort((a, b) => 
    a[n] === b[n] ? a.localeCompare(b) : a[n].localeCompare(b[n])
  );
}

45-2. 가독성보다 아름다움을

이런 풀이도 있다. charAt()이 처음에 시선을 잡을 수 있는데, 그냥 예전 자바스크립트의 표현 방식이고 실제로는 a[n]과 같다. 사실 더 주의깊게 볼 부분은 (a > b) - (a < b)부분이다.

javascript
function solution(strings, n) {
    return strings.sort((a, b) => {
        const chr1 = a.charAt(n);
        const chr2 = b.charAt(n);

        if (chr1 == chr2) {
            return (a > b) - (a < b);
        } else {
            return (chr1 > chr2) - (chr1 < chr2);
        }
    });
}

얼핏 보면 아주 헷갈리는데, 이런 의미다.

즉 a가 b보다 크면 1, a가 b보다 작으면 -1, 같으면 0을 반환해 localeCompare(a, b)와 같은 역할을 한다.

46. 명예의 전당(1)

이 문제는 1일차부터 이어지는 점수들의 배열 score와 자연수 k가 주어지면, 명예의 전당(k 순위까지 있음)의 마지막 순위 점수를 1일차부터 마지막 날까지 저장한 배열을 반환하는 문제다.

나는 아래와 같이 한번에 한 점수를 push하고 그때그때 소팅해서 마지막 순서에 있는 점수를 answer이라는 배열에 넣은 후 반환했다. 풀면서도 그때그때 소팅하는게 성능상 너무 안 좋다고 생각하긴 했지만, shift나 unshift가 아닌 push와 pop을 썼다는 것에 우선 만족했다.

javascript
function solution(k, score) {
    const answer = [];
    const hof = [];
    for(s of score){
        hof.push(s);
        hof.sort((a, b) => b - a);
        if(hof.length > k) hof.pop();
        answer.push(hof[hof.length - 1]);
    }

    return answer;
}

46-1. reduce 활용

아래와 같이 reduce를 활용한 풀이가 가능하다.

javascript
function solution(k, score){
    const answer = [];
    return score.reduce((a, c) => {
        answer.push(c);
        answer = answer.sort((a, b) => b - a).slice(0, k);
        return [...acc, Math.min(...answer)]
    }, [])
}

47. 카드 뭉치

이 문제는 단어들이 들어 있는 두 개의 배열을 받아서, 앞에서부터 순서대로 조합을 하여 goal의 문장을 만들 수 있으면 Yes, 아니면 No를 반환하는 문제다.

나는 이렇게 풀었다:

javascript
function solution(cards1, cards2, goal) {
    for(let i = 0; i < goal.length; i++){
        if(goal[i] === cards1[0]){
            cards1.shift();
            continue;
        } else if (goal[i] === cards2[0]){
            cards2.shift();
            continue;
        } else {
            return "No";
        }
    }
    return "Yes";
}

이 풀이는 물론 작동하지만, shift 메소드의 한계로 O(N ^ 2)까지 시간 복잡도가 증가할 수 있다.(for문 안에서 또 shift를 하다보니)

47-1. index를 활용하여 시간 복잡도 낮추기

꼭 배열을 변화시키지 않고도, 인덱스를 포인터로 이용해 비슷한 효과를 내면서 시간 복잡도도 낮출 수 있다.

javascript
function solution(cards1, cards2, goal) {
    let i = 0, j = 0;
    for (const word of goal) {
        if (i < cards1.length && word === cards1[i]) {
            i++;
        } else if (j < cards2.length && word === cards2[j]) {
            j++;
        } else {
            return "No";
        }
    }
    return "Yes";
}

48. 추억 점수

이 문제는 name에 해당하는 yearning 배열의 점수에 근거해, photo의 각 사진들의 추억 점수를 합해서 반환하라는 문제다.

나는 name을 키 값으로 하는 yearning 점수가 있는 객체를 만든 후, photo의 각 사진들에 reduce를 써서 해당 키 값의 점수들을 합쳤다.

javascript
function solution(name, yearning, photo) {
    const yearnMap = {};
    for(let i in name){
        yearnMap[name[i]] = yearning[i];
    }
    return photo.map((p) => p.reduce((acc, cur) => {
        if(yearnMap[cur]){
            return acc += yearnMap[cur];
        } else {
            return acc;
        }
    }, 0));
}

이 코드 자체에 수정을 좀 하자면, 우선 yearnMap[cur] === 0인 경우 물론 없기도 하고 더해도 0이지만, 습관적으로 if(yearnMap.hasOwnProperty(cur))을 쓰는 것이 보다 안전하다. 또는 if(cur in yearnMap)도 좋다.

또, 현재는 for문을 써서 yearnMap을 만들었지만 아래와 같이 쓰는 것이 가독성과 선언적 스타일을 높일 수 있다.

javascript
const yearnMap = Object.fromEntries(name.map((n, i) => [n, yearning[i]]));

또, reduce의 acc, cur보다 좀 더 직관적인 sum, person을 쓰는 것이 가독성이 좋다.

정리하면 아래와 같다:

javascript
function solution(name, yearning, photo) {
  const yearnMap = Object.fromEntries(name.map((n, i) => [n, yearning[i]]));

  return photo.map(p =>
    p.reduce((sum, person) =>
      sum + (person in yearnMap ? yearnMap[person] : 0), 0)
  );
}

48-1. indexOf로 그때그때 점수 찾기

reduce안에 자체적으로 indexOf를 활용해서 그때그때 점수를 찾아 더하는 방식도 있다.

javascript
function solution(name, yearning, photo) {
    return photo.map(v =>
        v.reduce((a, c) => a += yearning[name.indexOf(c)] ?? 0, 0)
    );
}

다만, 이 코드는 name.indexOf(c)가 photo안에 이름이 많으면 성능이 O(N^2)까지 뻗어나갈 수 있어 안 좋아진다. 객체를 쓰는 방식은 해시를 이용하기 때문에 O(1)로 유리하다.

49. [1차] 비밀지도

이 문제는 언뜻 보면 그래프를 써서 최단거리를 찾는 문제인척 하면서 사실은 그냥 이진수 변환 및 문자열 파싱 문제다. 숫자들의 배열이 주어지면 2진수로 변환 후 두 배열을 비교해 둘 다 공백(0)일때만 공백을 반환하는 문제다.

나는 이렇게 풀었는데, 계속 로깅하면서 지저분하게 풀었다. 2진법 문자열로 각 배열의 요소들을 변환한 후, 더해서 1 또는 2이면 #으로, 0이면 공백으로 바꾼 문자열을 반환하도록 map했다.

javascript
function solution(n, arr1, arr2) {
    const newArr1 = arr1.map(toBinary)
    const newArr2 = arr2.map(toBinary)
    const sum = newArr1.map((v, i) => Number(v) + Number(newArr2[i]))
    return sum.map((v, i) => {
        let str = String(v);
        if(str.length < n){
            str = "0".repeat(n - str.length) + str
        }
        return [...str].map(n => {
            if(n === "1" || n === "2"){
            return "#"
        } else{
            return " "
        }
        }).join("")
    })
}

const toBinary = (num) => {
        return String((num).toString(2));
}

49-1. 비트 연산자와 padStart

이진법 계산에 쓸 수 있는 비트 연산자 |(OR)와 자리수를 맞춰주는 padStart 함수를 쓴다면 굳이 숫자로 바꿨다가 다시 문자열로 바꿀 필요가 없다. | 연산자를 쓰면 각 자리수마다 1이 1개라도 있으면 1을 반환하고, padStart를 쓰면 처음에 0을 자동으로 n에 맞춰준다.

마지막으로 1일때는 전역 플래그로 #을, 0일때는 공백으로 replace하면 끝.

javascript
function solution(n, arr1, arr2) {
  return arr1.map((a, i) => {
    const binary = (a | arr2[i]).toString(2).padStart(n, '0');
    return binary.replace(/1/g, '#').replace(/0/g, ' ');
  });
}

50. 기사단원의 무기

이 문제는 1부터 주어진 매개변수 number까지의 숫자들의 약수의 개수들의 합을 구하되, limit을 초과하는 약수의 개수가 나오면 power로 대체해서 합을 구하는 문제다. 나는 처음에는 이렇게 풀었다:

javascript
function solution(number, limit, power) {
    const answer = [];
    for(let i = 1; i <= number; i++){
        answer.push(getDivNum(i));
    }
    return answer.map((v) => v > limit ? power : v).reduce((acc, cur) => acc += Number(cur), 0);
}

function getDivNum(num){
    let count = 0;
    for(let i = 1; i <= num; i++){
        if(num % i === 0) count++;
    }
    return count;
}

하지만 테스트 케이스들 중 시간 초과가 되는 경우들이 생기며 실패했다. 제한사항의 number는 100,000 이하이기 때문에, 비효율적으로 쓰인 getDivNum에 문제가 있다고 생각해서 아래와 같이 개선해보았다.

javascript
function getDivNum(num){
    if(num === 1) return 1;
    if(num === 2) return 2;
    let count = 2; // 1과 num 본인
    for(let i = 2; i <= Math.floor(num / 2); i++){
        if(num % i === 0) count++;
    }
    return count;
}

하지만 이걸론 여전히 부족했다.

50-1. 제곱근까지 약수 세기

약수의 개수는 해당 수의 제곱근까지만 세도 충분하다. 왜냐하면 해당 수의 제곱근 이전에 d라는 약수가 있다면, 제곱근 이후에 n/d라는 또다른 약수가 있으므로 d라는 약수에 대해 1번이 아니라 쌍 n/d까지 포함해 2번을 세면 되기 때문이다. 다만 완전제곱수가 있을 수 있으므로 이 경우 확인해서 d에 대해 1번을 세야 한다. 코드로는 아래와 같다.

javascript
function solution(number, limit, power) {
  let total = 0;

  for (let n = 1; n <= number; n++) {
    let count = 0;
    const root = Math.floor(Math.sqrt(n));

    for (let d = 1; d <= root; d++) {
      if (n % d === 0) {
        // d와 n/d가 약수 쌍
        count += (d * d === n) ? 1 : 2; // 완전제곱수면 1개, 아니면 2개
      }
    }

    total += (count > limit) ? power : count;
  }

  return total;
}

50-2. 배수 누적하기

소인수분해하는 방법 말고, 접근을 아예 달리해 각 정수 d의 배수들에 약수 1개를 더하는 방식으로 진행할 수도 있다. 즉, 1, 2, 3, 4, ... n까지 세가며 1의 배수 몇개, 2의 배수 몇개, 3의 배수 몇개... 하는 식으로 더하는 것이다.

javascript
function solution(number, limit, power) {
  const count = Array(number + 1).fill(0);

  // 모든 약수 개수 계산
  for (let d = 1; d <= number; d++) {
    for (let multiple = d; multiple <= number; multiple += d) count[multiple]++;
  }

  // 1번부터
  return count.slice(1).reduce((sum, cnt) => sum + (cnt > limit ? power : cnt), 0);
}