2.5프로그래머스 Lv.1 #61~70

개요

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

61. 로또의 최고 순위와 최저 순위

로또의 최고 순위와 최저 순위는 로또 당첨 번호의 목록과 찍은 번호의 목록이 주어질 때, 찍은 번호 중 낙서가 되어 알아볼 수 없는 번호가 0으로 주어지면 가능한 최고 등수와 최하 등수가 어떻게 되는지 구하는 문제다.

배열보다 set가 접근이 빠를것 같아, set으로 로또 당첨 번호를 바꾸고 해당 번호를 순회하며 확실한 번호들의 개수 및 0의 개수를 세서 최고 시나리오(0이 다 정답일 경우)와 최악 시나리오(0이 모두 빗나갈 경우)를 구했다.

6등부터 시작하는지라, 예외 케이스들(전부 틀렸을 때)에 대해 조건 처리도 필요했다.

javascript
function solution(lottos, win_nums) {
    const winSet = new Set(win_nums);

    let numZero = 0;
    let numConfirmed = 0;
    for(let i = 0; i < lottos.length; i++){
        if(winSet.has(lottos[i])) numConfirmed++;
        if(lottos[i] === 0) numZero++;
    }
    
    const best = numConfirmed === 0 && numZero === 0 ? 6 : 7 - (numConfirmed + numZero);
    const worst = numConfirmed === 0 ? 6 : 7 - numConfirmed;
    return [best, worst];
}

61-1. filter로 for 대체 및 배열로 rank 처리하기

위의 코드는 실행은 되지만, 리팩토링하면 더 좋을 부분들이 있다.

1. 정답 개수와 0의 개수를 for문이 아닌 filter와 Array.length로 간단하게 처리 가능하다.
2. 등수 처리를 배열로 할 수 있다. 특히, 예외 케이스에 대해서도 아래와 같은 방식으로 처리 가능하다.

javascript
function solution(lottos, win_nums) {
  const winSet = new Set(win_nums);

  const matches = lottos.filter(x => winSet.has(x)).length;
  const zeros   = lottos.filter(x => x === 0).length;

  const rank = [6, 6, 5, 4, 3, 2, 1]; // 맞힌 개수 -> 등수 매핑
  return [rank[matches + zeros], rank[matches]];
}

62. 둘만의 암호

둘만의 암호는 문자열 파싱 문제로, 시저 암호와 비슷하게 문자열 s를 받고 index를 받으면 s의 각 문자에 대해서 index만큼 밀린 문자열을 반환하되, skip에 있는 문자들은 건너뛰면서 문자를 밀어야 하는 문제다.

기존에 다른 비슷한 문제들을 풀면서 느낀건 charCodeAt()보단 abcd...를 다 입력하는게 더 쉽다는 것. 아래와 같이 풀었다.

javascript
function solution(s, skip, index) {
    const alphabet = "abcdefghijklmnopqrstuvwxyz";
    const skipped = [...alphabet].filter(ch => !skip.includes(ch)).join("");
    const answer = [];
    for(let i = 0; i < s.length; i++){
        answer.push(skipped[(skipped.indexOf(s[i]) + index) % skipped.length]);
    }
    return answer.join("");
}

62-1. 리팩토링: set 활용

이 코드 역시 여러가지로 고칠 수 있겠지만, 가장 우선적으로 고칠 수 있는 부분은 for문 안의 indexOf다. 매 문자마다 indexOf를 부르는것보다 한번에 문자 → 인덱스 맵을 만들어두면 더 깔끔해진다.

또, 배열에서 includes를 하는것보다 Set에서 has 메소드를 부르는 것이 성능상으로나, 의도가 보이는데서나 더 좋은 코딩이다.

마지막으로, answer.push를 한 후 answer.join("")으로 합하는것보다 한번에 map(...)과 join("")으로 압축할 수도 있다.

javascript
function solution(s, skip, index) {
  const skipSet = new Set(skip);
  const ring = []; // 사용 가능한 알파벳 고리
  for (let c = 97; c <= 122; c++) {
    const ch = String.fromCharCode(c);
    if (!skipSet.has(ch)) ring.push(ch);
  }

  const pos = Object.fromEntries(ring.map((ch, i) => [ch, i])); // 문자→인덱스 맵
  const L = ring.length;
  const shift = index % L;

  return [...s].map(ch => ring[(pos[ch] + shift) % L]).join('');
}

62-2. 정규표현식

정규표현식을 여기서도 쓸 수 있다. match 메소드와 ^를 활용해 해당 문자열에 있는 문자들은 포함하지 않는 문자열을 구성할 수 있고, 이걸로 인덱스를 더해 각 문자를 암호화할 수 있다.

javascript
const solution = (s, skip, index) => {
  let ans = '';
  const matched = 'abcdefghijklmnopqrstuvwxyz'.match(
    new RegExp(`[^${skip}]`, 'g'),
  );
  for (const c of s) {
    const newIdx = matched.indexOf(c) + index;
    ans += matched[newIdx % matched.length];
  }
  return ans;
};

63. 문자열 나누기

문자열 나누기는 문자열 s가 주어졌을 때 약간 복잡한 규칙(..)을 통해 분해한 문자열의 개수를 반환하는 문제다. 포인터를 만들고 카운터를 만들고 for문을 통해 해당 문자열을 순회하며 풀었는데, 기억하고자 남긴다.

javascript
function solution(s) {
    let answer = 0, pointer = null, same = 0, diff = 0;
    for(const ch of s){
        if(!pointer){
            pointer = ch;
            same = 1;
            diff = 0;
        } else {
            if(ch === pointer) same++;
            else diff++;
        }
        
        if(same === diff){
            answer++;
            pointer = null;
            same = 0;
            diff = 0;
        }
    }
    
    if(pointer !== null) answer++;
    return answer;
}

66. 체육복

체육복은 전체 학생의 수 n과 체육복을 도난당한 학생들의 배열 lost, 여벌을 챙겨온 학생 reserve가 주어졌고 학생들은 체격이 번호 순서대로라서 1씩 차이나는 학생에겐 빌려줄 수 있다고 할 때, 수업에 참여할 수 있는 학생의 최댓값을 반환하는 함수를 쓰는 문제다.

이 문제는 중요 포인트가 하나 있는데, 여벌을 가져온 학생이 정작 본인의 체육복은 도난당했을 수 있고 그 때는 다른 사람에게 빌려주지 않고 자신이 입는다는 것이다. 아래 코드는 처음에 작성해서 다 푼 줄 알았는데, 이 부분을 제대로 처리하지 못했던 코드다.

javascript
function solution(n, lost, reserve) {
    const current = n - lost.length;
    const sorted = lost.sort((a, b) => a - b);
    const reserveSet = new Set(reserve);
    let answer = current;
    for(l of sorted){
        if(reserveSet.has(l)){
            reserveSet.delete(l);
            answer++;
            continue;
        } else if(reserveSet.has(l - 1)){
            reserveSet.delete(l - 1);
            answer++;
            continue;
        } else if(reserveSet.has(l + 1)){
            reserveSet.delete(l + 1);
            answer++;
            continue;
        }
    }
    return answer;
}

나는 나름 reserveSet.has(l)을 포함해서 여벌 체육복을 가져온 학생이 도난당한 케이스를 방지했다고 생각했는데, 예를 들어 n = 5, lost = [2, 3], reserve = [3, 4]인 경우 3번 학생이 2번 학생에게 여벌 체육복을, 4번 학생이 3번 학생에게 여벌 체육복을 빌려주는 경우는 사실 생기지 않는다. 왜냐하면 3번 학생은 다른 학생에게 빌려주지 않고 자신이 입기 때문이다.

이런 경우는 반례를 생각하지 못했다기보단 문제의 요구사항을 정확히 반영하지 않은 코드를 작성했기 때문에 생긴 빈틈이라고 생각한다.

따라서 아래와 같이 둘 다 set으로 만들어 답을 수정했다.

javascript
function solution(n, lost, reserve) {
    const lostSet = new Set(lost);
    const reserveSet = new Set(reserve);
    for(const l of lostSet){
        if(reserveSet.has(l)){
            reserveSet.delete(l);
            lostSet.delete(l)
        };
    }
    let answer = n - lostSet.size;
    const sorted = [...lostSet].sort((a, b) => a - b);
    
    for(l of sorted){
        if(reserveSet.has(l - 1)){
            reserveSet.delete(l - 1);
            answer++;
            continue;
        } else if(reserveSet.has(l + 1)){
            reserveSet.delete(l + 1);
            answer++;
            continue;
        }
    }
    return answer;
}

66-1. 배열 메소드로 풀기

같은 왼쪽 우선 그리디 방식을 유지하되 배열 메소드로 풀 수 있다.

javascript
function solution(n, lost, reserve) {
  // 1) 겹치는 학생 제거
  let r = reserve.filter(x => !lost.includes(x)).sort((a, b) => a - b);
  let l = lost.filter(x => !reserve.includes(x)).sort((a, b) => a - b);

  // 2) 빌릴 수 없는 사람만 남기기 (왼쪽 우선)
  const remain = l.filter(a => {
    // 왼쪽 먼저, 없으면 오른쪽
    let b = r.find(v => v === a - 1) ?? r.find(v => v === a + 1);
    if (!b) return true;              // 못 빌리면 남김
    r = r.filter(v => v !== b);       // 빌린 여벌 제거
    return false;                     // 빌렸으니 제외
  });

  return n - remain.length;
}

67. 숫자 짝꿍

숫자 짝꿍은 두 정수 X, Y가 주어졌을때 공통으로 나타나는 정수들을 이용해 만들 수 있는 가장 큰 정수를 문자열 형태로 반환하는 문제다.

나는 처음에 이렇게 풀었다. 아니, 정말 처음에는 마지막 코드를 Number()로 숫자로 바꿔주는 형태로 썼지만 제한사항에서 자릿수가 무려 300만까지였기에 에러가 발생, BigInt()로 바꾸었다.

하지만 이 풀이는 일부 테스트 케이스에서 시간초과 오류가 났다. 효율적이지 않은 코드란 의미다.

javascript
function solution(X, Y) {
    const mapX = new Map();
    const mapY = new Map();
    for(const n of [...X]){
        if(!mapX.get(n)){
            mapX.set(n, 1);
        } else{
            mapX.set(n, mapX.get(n) + 1);            
        }
    }
    for(const m of [...Y]){
        if(!mapY.get(m)){
            mapY.set(m, 1);
        } else{
            mapY.set(m, mapY.get(m) + 1);            
        }
    }
    const combinedMap = new Map();
    for(const [num, count] of mapX){
        if(mapY.get(num)){
            combinedMap.set(num, Math.min(mapX.get(num), mapY.get(num)));
        }
    }
    const combinedArr = [];
    for(const [numCbd, countCbd] of combinedMap){
        for(i = 1; i <= countCbd; i++){
            combinedArr.push(numCbd)    
        }
    }
    const answer = combinedArr.sort((a, b) => b - a).join("")
    if(!combinedArr.length) return "-1";
    return String(BigInt(answer));
}

67-1. 정렬 비용 개선

위의 로직을 효율적으로 고쳐보자.

우선 가장 큰 부분부터. 자바스크립트 내장 정렬은 O(N log N)이기 때문에 이 방식으론 시간 초과가 난다. 어차피 키 값이 0 ~ 9로 정해져있으니, Map이어도 다시 배열로 바꿔 소팅할 필요 없고 key를 9부터 시작해 0으로 내리며 숫자를 바로 붙이면 된다.

다음으로, map을 만들 때도 굳이 [...X] 식으로 스프레드 할 필요가 없고 바로 for...of로 하는 것이 공간 복잡도를 줄이는데 도움이 된다. 또, 이 과정에서 if...else문 대신 조건 연산자를 통해 보다 가독성 있는 코드를 작성할 수 있다.

javascript
function solution(X, Y){
    const mapX = new Map();
    const mapY = new Map();

    for(const ch of X) mapX.set(ch, (mapX.get(ch) ?? 0) + 1);
    for(const ch of Y) mapY.set(ch, (mapY.get(ch) ?? 0) + 1);

    // 큰 숫자부터 바로 붙이기(정렬 안해도 됨)
    let res = '';
    for(let d = 9; d >= 0; d--){
        const key = String(d);
        const cnt = Math.min(mapX.get(key) ?? 0, mapY.get(key) ?? 0);
        if(cnt > 0) res += key.repeat(cnt);
    }

    if(res === '') return '-1';
    if(res[0] === '0') return '0'; // 0이 가장 큰 경우, "000" 등 방지
    return res;
}

67-2. 배열 사용하기

비슷한 로직이지만, 숫자가 0 ~ 9까지 10개 뿐이므로 빈도를 세는 배열을 만들어 해결할 수도 있다.

javascript
function solution(X, Y) {
  const cntX = Array(10).fill(0);
  const cntY = Array(10).fill(0);

  for (let i = 0; i < X.length; i++) cntX[Number(X[i])]++;
  for (let i = 0; i < Y.length; i++) cntY[Number(Y[i])]++;

  let res = '';
  for (let d = 9; d >= 0; d--) {
    const c = Math.min(cntX[d], cntY[d]);
    if (c > 0) res += String(d).repeat(c);
  }

  if (res === '') return '-1';
  if (res[0] === '0') return '0';
  return res;
}

68. 햄버거 만들기

햄버거 만들기는 1, 2, 3 중 하나인 원소들로 쭉 이어진 배열에서 1, 2, 3, 1이라는 패턴이 나오면 제거하고, 그렇게 제거하고 나서 1, 2, 3, 1이 발견되면 또 제거하고...하는 식으로 진행할때 주어진 배열에서 얼마나 많이 제거할 수 있는지 구하는 함수를 작성하는 문제다.

위에 쌓고 위에서부터 빼는 것이니 스택 문제로 판단, array를 활용해 스택처럼 썼다.

javascript
function solution(ingredient) {
    const stack = [];
    let counter = 0;
    
    for(i of ingredient){
        stack.push(i);
        const len = stack.length;
        
        if(len >= 4 &&
          stack[len - 1] === 1 &&
          stack[len - 2] === 3 &&
          stack[len - 3] === 2 &&
          stack[len - 4] === 1
          ){
            stack.pop();
            stack.pop();
            stack.pop();
            stack.pop();
            counter++;
           }   
    }
    return counter;
}

여기서 pop을 4번 연속으로 썼는데, 사실 아래와 같이 써도 되지만 4번 정도면 그냥 풀어 쓰는게 더 직관적으로 보이기도 해서 그렇게 썼다.

javascript
for(let i = 0; i < 4; i++) stack.pop();

그런데 더 좋은 방법이 있다.

javascript
stack.length = len - 4;

이 방법은 배열 크기를 강제로 줄여버려서, 마지막 4개 요소가 잘린다. 불필요한 반환이 없이 아주 빠르고 효율적인 것이다.

또, splice도 있다. 음수 인덱스가 적용되는 splice는 가독성도 좋고 명령 한 줄로 잘리지만, 잘라낸 부분을 배열로 반환하므로 불필요한 배열 생성(메모리 낭비)이 있다. 이로 인해 미세하게 느려지는것도 단점.

javascript
stack.splice(-4);

68-1. for문으로 해결

for문 한번으로 끝낼 수 있다. 비결은 i를 계속 올리면서, 조건문을 성립시키면 카운터도 올리고 배열도 변환, i는 3씩 낮추는 것.

javascript
function solution(ingredient) {
    let count = 0;

    for (let i = 0; i < ingredient.length; i++) {
        if (ingredient.slice(i, i + 4).join('') === '1231') {
            count++;
            ingredient.splice(i, 4);
            i -= 3;
        }
    }

    return count;
}

69. 크레인 인형뽑기 게임

인형뽑기는 중첩 배열로 표현되는 보드판에 인형들을 표현하고 어디서 인형을 뽑는지가 순서대로 적힌 moves라는 배열이 나올 때, 뽑은 인형들이 연속으로 놓이면 없어지는 규칙이 있다면 moves를 모두 실행하면 인형이 총 몇개 없어지는지 묻는 문제다.

javascript
function solution(board, moves) {
    const stack = [];
    let prev = null;
    let answer = 0;
    
    for(const m of moves){
        const idx = m - 1;
        for(const b of board){
            // 0이면 통과
            if(b[idx] === 0) continue;
            
            // 스택의 맨 마지막에 해당 인형이 있으면 삭제
            if(stack[stack.length - 1] === b[idx]){
                answer += 2;
                stack.pop();
                prev = stack[stack.length - 1] ?? null;
            } else{
                // 해당 인형 아니면 추가
                stack.push(b[idx]);
                prev = b[idx];
            }
            b[idx] = 0;
            break;
        }
    }
    return answer;
}

69-1. 개선

물론 근본부터 개선할 수 있다(69-2 참고). 하지만 우선 위의 코드부터 리팩토링해보자.

우선, idx, b 보다 좀 더 의미가 드러나는 변수명을 쓰는게 좋다. 또, prev를 습관처럼 썼는데 이 풀이에선 스택을 관리하므로 쓸 필요가 없다.

javascript
function solution(board, moves){
    const stack = [];
    let removed = 0;

    for(const m of moves){
        const col = m - 1;
        for(const row of board){
            const doll = row[col];
            if(doll === 0) continue; // 빈칸이면 다음 행

            row[col] = 0; // 집어 올리면서 변경
            if(stack.length && stack[stack.length - 1] === doll){
                stack.pop();
                removed += 2;
            } else {
                stack.push(doll);
            }
            break;
        }
    }
    return removed;
}

69-2. 열을 스택으로 만들기

위의 방식은 열마다 위에서부터 빈칸을 건너뛰면서 찾는 방식이므로 move당 최악의 경우 O(N)이 걸린다. 각 열을 스택으로 만들어두고 매 move마다 pop만 하면 O(1)로 성능을 개선할 수 있다.

javascript
function solution(board, moves){
    const n = board.length;
    const colStacks = Array.from({length: n}, () => []);

    // 각 열마다 아래에서 위로 훑으며 인형들 쌓은 스택 만들기
    for(let col = 0; col < n; col++){
        for(let row = n - 1; row >= 0; row--){
            const v = board[row][col];
            if(v !== 0) colStacks[col].push(v);
        }
    }
    
    const basket = [];
    let removed = 0;

    for(const m of moves){
        const col = m - 1;
        const stack = colStacks[col];
        if(!stack.length) continue; // 인형 없는 열

        const doll = stack.pop();
        if(basket.length && basket[basket.length - 1] === doll){
            basket.pop();
            removed += 2;
        } else {
            basket.push(doll);
        }
    }

    return removed;
}

69-3. transpose로 행열을 바꾸기 스택 활용

보드 데이터의 각 배열이 가로줄이기 때문에 실제 인형을 뽑는 세로줄과는 차이가 있으므로 이걸 고치는 transpose 함수를 만들고, 스택으로 문제를 푼 답이 보여 가져왔다. 처음에 나도 이 방향을 생각하긴 했으나 2중 for문을 쓰면 그렇게 안 해도 된다는 사실을 깨닫고 위와 같이 풀었다.

javascript
// const transpose = matrix =>
//     matrix.reduce(
//         (result, row) => row.map((_, i) => [...(result[i] || []), row[i]]),
//         []
//     );

const transpose = (matrix) => {
    const R = matrix.length, C = matrix[0].length;
    const res = Array.from({length: C}, () => Array(R));
    for(let r = 0; r < R; r++){
        for(let c = 0; c < C; c++) res[c][r] = mat[r][c];
    }
    return res;
}

const solution = (board, moves) => {
    const stacks = transpose(board).map(col =>{
        const s = [];
        for(let i = col.length - 1; i >= 0; i--) if(col[i] !== 0) s.push(col[i]);
        return s;
    });

    const basket = [];
    let result = 0;

    for (const move of moves) {
        const pop = stacks[move - 1].pop();
        if (!pop) continue;
        if (pop === basket[basket.length - 1]) {
            basket.pop();
            result += 2;
            continue;
        }
        basket.push(pop);
    }

    return result;
};

70. 성격 유형 검사하기

성격 유형 검사하기는 MBTI와 비슷한 가상의 테스트 문제들과 그 각 문제들에 대한 선택값들을 choices라는 배열로 받으면 MBTI 결과를 반환하는 문제다.

나는 이렇게 풀었다. 우선 어차피 유형들은 다 정해져있으므로 각각의 유형에 대해 모두 0점인 결과지를 만들고, 점수를 for문으로 매긴다. 이후 점수를 보고 각 유형별로 더 큰 점수를 얻은 유형들을 순서대로 이어붙인다.

javascript
function solution(survey, choices) {
    const score = {A: 0, N: 0, C: 0, F: 0, M: 0, J: 0, R: 0, T: 0};
    for(let i = 0; i < survey.length; i++){
        if(choices[i] > 4){
            score[survey[i][1]] += choices[i] - 4;
        } else if(choices[i] < 4){
            score[survey[i][0]] += 4 - choices[i]
        }
    }
    const rt = score["T"] > score["R"] ? "T" : "R"
    const cf = score["F"] > score["C"] ? "F" : "C"
    const jm = score["M"] > score["J"] ? "M" : "J"
    const an = score["N"] > score["A"] ? "N" : "A"
    return rt + cf + jm + an;
}

70-1. 개선

일부 하드코딩된 부분들을 줄이고 가독성을 개선해보자.

우선, 왼쪽, 오른쪽을 survey[i][0]식으로 적는것보다 한번 deconstructuring 해서 쓸 수 있다. 또, 4점 기준으로 +, -되는것에 대해 4를 빼고 양수면 더하고 음수면 빼는 식으로 코드를 작성할 수 있다. 마지막으로, 문자열을 만들때도 성격을 알려주는 문자들의 쌍을 만들어 점수를 비교하고 반환하는 것을 한번에 map 메소드로 처리할 수 있다.

javascript
function solution(survey, choices) {
  const score = { A:0, N:0, C:0, F:0, M:0, J:0, R:0, T:0 };
  // const score = Object.fromEntries("RTCFJMAN".split("").map(c => [c, 0])); 이렇게 할 수도 있다

  for (let i = 0; i < survey.length; i++) {
    const [L, R] = survey[i];
    const d = choices[i] - 4;          // -3..+3
    if (d > 0) score[R] += d;          // 동의 쪽(R)에 d점
    else if (d < 0) score[L] += -d;    // 비동의 쪽(L)에 -d점
  }

  const pairs = [['R','T'], ['C','F'], ['J','M'], ['A','N']];
  return pairs.map(([a, b]) => (score[a] >= score[b] ? a : b)).join('');
}