sungyup's.

algorithm_programmers / Lv.1 / 2.4 프로그래머스 Lv.1 #51~60

2.4프로그래머스 Lv.1 #51~60

프로그래머스 Lv.1 51~60번

개요

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

53. 모의고사

모의고사는 수포자 3명이 서로 다른 주어진 찍는 방식을 가졌을 때, 문제들의 답이 주어지면 가장 고득점 수포자(들)의 번호를 반환하는 문제다.

나는 우선 각 수포자들의 찍는 패턴을 저장하고, answers 배열에 forEach를 적용해 일치하면 각각의 카운터를 1씩 올렸다. 이후, 카운터들을 배열로 묶은 후 map과 filter로 최댓값과 일치하는 인덱스들을 반환하고 null값을 배제했다:

javascript
function solution(answers) {
    const supo1 = [1, 2, 3, 4, 5];
    const supo2 = [2, 1, 2, 3, 2, 4, 2, 5];
    const supo3 = [3, 3, 1, 1, 2, 2, 4, 4, 5, 5];
    let count1 =0, count2 = 0, count3 = 0;
    
    answers.forEach((v, i) => {
        if(v === supo1[i % 5]) count1++
        if(v === supo2[i % 8]) count2++
        if(v === supo3[i % 10]) count3++
    })
    return [count1, count2, count3].map((v, i)=> {
        if(v === Math.max(count1, count2, count3)){
            return i + 1;        
        } else {
            return;
        }
    }).filter(v => v)
}

53-1. 묶을건 묶기

supo1, 2, 3이나 count1, 2, 3으로 모두 별개의 저장공간을 쓰기보다는 하나로 묶는게 더 깔끔하다.

javascript
function solution(answers) {
  const patterns = [
    [1, 2, 3, 4, 5],
    [2, 1, 2, 3, 2, 4, 2, 5],
    [3, 3, 1, 1, 2, 2, 4, 4, 5, 5],
  ];

  const counts = [0, 0, 0];

  // 정답 채점
  for (let i = 0; i < answers.length; i++) {
    const a = answers[i];
    if (a === patterns[0][i % patterns[0].length]) counts[0]++;
    if (a === patterns[1][i % patterns[1].length]) counts[1]++;
    if (a === patterns[2][i % patterns[2].length]) counts[2]++;
  }

  const maxScore = Math.max(...counts);

  // 최댓값과 같은 수포자만 오름차순으로 반환
  const result = [];
  for (let i = 0; i < counts.length; i++) {
    if (counts[i] === maxScore) result.push(i + 1);
  }
  return result;
}

54. 덧칠하기

덧칠하기는 길이가 n인 벽에 길이가 m인 롤러로 색칠할 때, 색칠이 안 된 벽의 위치들의 정보가 담긴 배열 section이 주어지면 최소 몇번 색칠해야 벽을 모두 칠할 수 있는지 구할 수 있는 함수를 작성하는 문제다.

나는 우선 n + 1길이의 배열을 만들고(그래야 배열의 인덱스가 섹션으로 주어지는 인덱스와 일치하므로) 모두 true로 우선 채우고, section에 주어진 인덱스는 모두 false로 표시했다. 그리고 인덱스를 받으면 인덱스로부터 길이만큼 색칠하는(배열에 true로 바꾸는) 함수를 작성하고, 색칠 여부를 저장한 배열의 1번 인덱스부터 끝까지 순회하며 색칠이 안된 경우 색칠하는 함수를 수행하고 카운터를 올린 후, 마지막에 카운터를 반환했다.

javascript
function solution(n, m, section) {
    const arr = Array(n + 1).fill(true);
    function paint(begin){
        for(let i = begin; i < begin + m; i++){
            arr[i] = true;
        }
    }

    let answer = 0;
    for(s of section){
        arr[s] = false;
    }
    for(let i = 1; i <= n + 1; i++){
        if(arr[i] === false) {
            paint(i);
            answer++;
        };
    }
    
    return answer;
}

54-1. 보다 깔끔한 풀이

근본적인 아이디어는 같지만, 좀 더 깔끔하게 풀 수 있다.

  1. 별도 함수나 배열을 작성할 필요 없이 하나의 for문과 어디까지 칠했는지를 관리하는 변수 하나만을 이용한다.
  2. 왼쪽부터 보다가 칠해야 하는 구역을 만나면, 거기서 길이 m만큼 칠하고, 그렇게 칠한 범위는 건너뛴다.
javascript
function solution(n, m, section) {
  let count = 0;
  let coverUntil = 0;              // 현재까지 칠해진 마지막 구역 번호

  for (const s of section) {       // section은 오름차순
    if (s > coverUntil) {          // 아직 칠해지지 않았다면
      count++;                     // 롤러 1번 더 칠하고
      coverUntil = s + m - 1;      // s부터 m칸 커버
    }
  }
  return count;
}

57. 소수 찾기

소수 찾기는 n이라는 숫자가 주어지면 1부터 n까지의 소수의 개수를 찾는 문제다.

처음에는 단순하게 n까지 올려가며, 해당 수마다 1부터 올려가며 나누며 끝까지 약수가 2개면 소수, 약수 개수가 2개를 넘어가면 다음수로 넘어가는 식으로 코드를 작성했다. 하지만 시간 초과였다.

javascript
function solution(n) {
    let answer = 0;
    for(let i = 2; i <= n; i++){
        let count = 0;
        for(let j = 1; j <= i; j++){
            if(count > 2) continue;
            if(i % j === 0) count++;
        }
        if(count === 2) answer++;
    }
    return answer;
}

57-1. 에라토스테네스의 체

수학적 지식을 활용해, 에라토스테네스의 체를 코드로 구현할 수 있다. 이 방법은 간단히 말해서, n이하의 소수를 모두 찾을때 2의 배수, 3의 배수, 5의 배수, ...하면서 다 지우는 방식이다.

javascript
function solution(n) {
  // true = 소수 후보
  const isPrime = Array(n + 1).fill(true);
  isPrime[0] = isPrime[1] = false;

  // p의 배수 지우기 (p*p부터)
  for (let p = 2; p * p <= n; p++) {
    if (!isPrime[p]) continue;
    for (let m = p * p; m <= n; m += p) {
      isPrime[m] = false;
    }
  }

  // 남아있는 true 개수 = 소수 개수
  let count = 0;
  for (let i = 2; i <= n; i++) if (isPrime[i]) count++;
  return count;
}

58. 옹알이(2)

옹알이(2)는 특정 발음들만 가능한 아이가 babbling이라는 문자열들의 배열이 주어지면 발음 가능하다고 주어진 발음만을 조합해서 해당 문자열들 중 몇 개를 발음할 수 있는지를 구하는 문제다. 여기서, 네 가지 발음이 주어지는데 두 번 연속 올 수는 없다.

처음에, 깔끔하지 않다고 생각하면서도 아래와 같이 풀었다. 논리는, 우선 가능한 발음들만 모은 배열을 하나 마련하고, 각각에 대해 연속으로 발음이 있는 경우를 제외한다. 이후, 제외할 문자열들은 제외한 babbling 배열에서 가능한 발음들은 모두 ""로 바꾼다. 이후, 결과가 ""라면 카운트를 1씩 늘려 최종 카운트를 반환한다.

javascript
function solution(babbling) {
    let answer = 0;
    const dict = ["aya", "ye", "woo", "ma"];
    const exclude = ["ayaaya", "yeye", "woowoo", "mama"];
    const excluded = babbling.filter(b => {
        return exclude.every(e => !b.includes(e))
    });
    for(let i in excluded){
        for(let d of dict){
            excluded[i] = excluded[i].replaceAll(d, "");
        }
    }
    for(let result of excluded){
        if(result === "") answer++;
    }
    return answer;
}

이 풀이는 기본 테스트는 통과했지만, 최종 테스트는 통과하지 못했다. 그 이유를 찾는데 오랜 시간이 걸렸는데, 예를 들어 "wayaoo"같은 경우는 우선 "aya"를 지우고 나면 "woo"가 남으므로 이게 또 지워져 카운트를 올리게 되기 때문이었다.

따라서 왼쪽부터 순차적으로 진행하며 dict에 있는 음절이 나오면 제거하고, 만약 끝까지 진행되었으면 true를 반환하는 형식으로 코드를 고쳐서 풀었다.

javascript
function solution(babbling) {
    let answer = 0;
    const dict = ["aya", "ye", "woo", "ma"];
    
    function canPronounce(word, prev = ""){
        if(word.length === 0) return true;
        for(const syllable of dict){
            if(syllable === prev) continue;
            if(word.startsWith(syllable)){
                if(canPronounce(word.slice(syllable.length), syllable))
                    return true;
            }
        }
        return false;
    }
    for(const babble of babbling){
        if(canPronounce(babble)){
            answer++;
        }
    }
    return answer;
}

이 풀이는 꼭 재귀로 할 필요는 없다. 아래와 같이 while문으로도 풀 수 있다.

javascript
function solution(babbling){
  const dict = ["aya", "ye", "woo", "ma"];
  let cnt = 0;

  for(const w of babbling){
    let i = 0, prev = "", ok = true;
    while(i < w.length){
      let hit = false;
      for(const s of dict){
        if(d === prev) continue; // 같은 음절 연속 금지
        if(w.startsWith(s, i)){ // 현재 i에서 s가 맞으면 해당 s 제거
          i+= s.length;
          prev = s;
          hit = true;
          break;
        }
      }
      if(!hit) {
        ok = false;
        break;
      }
    }
    if(ok) cnt++;
  }
  return cnt;
}

58-1. 정규표현식

이 문제는 정규표현식이 잘 어울리는 문제다. 포함되어야하는 문자열들을 담고, 연속으로 문자열이 들어갔는지 확인하는 test에선 false가, 시작부터 끝까지 모두 포함되어야하는 문자열만으로 구성되었는지 확인하는 test에선 true가 반환되어야 한다.

javascript
function solution(babbling) {
  const regexp1 = /(aya|ye|woo|ma)\1+/;
  const regexp2 = /^(aya|ye|woo|ma)+$/;

  return babbling.reduce((ans, word) => (
    !regexp1.test(word) && regexp2.test(word) ? ++ans : ans
  ), 0);
  // 또는, 아래와 같이
  // let count = 0;
  // for (const w of babbling) {
  //   if (twice.test(w)) continue;
  //   if (only.test(w)) count++;
  // }
  // return count;
}

59. 실패율

실패율은 총 스테이지 수 N, 유저별로 어느 스테이지에 막혀있는지 알려주는 배열 stages가 주어지면 실패율(도전한 유저 대비 여전히 해당 스테이지에 막힌 유저의 비율) 순서대로 스테이지를 정렬한 배열을 반환하는 함수를 작성하는 문제다.

나는 이렇게 풀었다:

  1. 스테이지별로 실패율을 저장하기 위해 배열을 만들었다.
  2. 여기서, 끝까지 통과하면 n + 1에 막힌걸로 저장되기 때문에 인덱스와 스테이지 번호를 맞추고 n + 1 스테이지 통과도 기록해야 하니 n + 2 크기의 배열을 만들고, 스테이지별 막혀있는 사람들을 기록하는 frequency counter로 활용한다.
  3. 남아 있는 사람수를 저장하는 변수를 만들고, 스테이지를 1부터 N까지 순회하며 앞서 본 막혀있는 사람/남아 있는 사람수로 실패율을 계산해 넣는다.
  4. 해당 배열을 소팅하고 키들을 반환한다.
javascript
function solution(N, stages) {
    const answer = [];
    const record = Array(N + 2).fill(0);
    for(const stage of stages) record[stage]++;
    
    let remaining = stages.length;
    for(let i = 1; i <= N; i++){
        answer.push({key: i, failRate: record[i] / remaining});
        remaining -= record[i];
    }
    answer.sort((a, b) => b.failRate - a.failRate)
    return answer.map((o) => o.key);
}

59-1. 객체가 아닌 배열로

배열로 푼 답안이 있는데, 잘 읽혀서 가져왔다.

javascript
function solution(N, stages) {
    let result = [];
    for(let i=1; i<=N; i++){
        let reach = stages.filter((x) => x >= i).length;
        let curr = stages.filter((x) => x === i).length;
        result.push([i, curr/reach]);
    }
    result.sort((a,b) => b[1] - a[1]);
    return result.map((x) => x[0]);
}

60. [1차] 다트 게임

다트 게임은 약간 복잡한 규칙으로 이루어진 문자열을 파싱해서 점수를 구하는 문제다. 보자마자 정규표현식이 떠올랐고, 정규표현식의 matchAll을 처음으로 써봐서 계속 로깅하면서 풀었다.

javascript
function solution(dartResult) {
    const rounds = [...dartResult.matchAll(/(\d{1,2})([SDT])([*#]?)/g)];
    const scores = [];
    for(let i = 0; i < rounds.length; i++){
        const [_, num, bonus, option] = rounds[i];
        let score = Number(num);
        
        if(bonus === "D"){
            score = score ** 2;
        } else if(bonus === "T"){
            score = score ** 3;
        }
        if(option === "#"){
            score *= (-1);
        } else if(option === "*"){
            score *= 2;
            if(i > 0) scores[i - 1] *= 2;
        }
        scores.push(score);
    }
    return scores.reduce((acc, cur) => acc += cur, 0);
}
Previous프로그래머스 Lv.1 #41~50
ITJavascript
Next프로그래머스 Lv.1 #61~70
ITJavascript