Skip to content

모의고사.md

Latest commit

 

History

History
179 lines (135 loc) · 6.53 KB

모의고사.md

File metadata and controls

179 lines (135 loc) · 6.53 KB
Raw

완전탐색: 모의고사

프로그래머스

요구사항

1번 수포자가 찍는 방식: 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, ...

2번 수포자가 찍는 방식: 2, 1, 2, 3, 2, 4, 2, 5, 2, 1, 2, 3, 2, 4, 2, 5, ...

3번 수포자가 찍는 방식: 3, 3, 1, 1, 2, 2, 4, 4, 5, 5, 3, 3, 1, 1, 2, 2, 4, 4, 5, 5, ...

1번 문제부터 마지막 문제까지의 정답이 순서대로 들은 배열 answers가 주어졌을 때, 가장 많은 문제를 맞힌 사람이 누구인지 배열에 담아 return 하도록 solution 함수를 작성해주세요.

제한 조건

  • 시험은 최대 10,000 문제로 구성되어있습니다.
  • 문제의 정답은 1, 2, 3, 4, 5중 하나입니다.
  • 가장 높은 점수를 받은 사람이 여럿일 경우, return하는 값을 오름차순 정렬해주세요.

첫 번째 제출 코드

function solution(answers) {
  const pattern1 = [1, 2, 3, 4, 5];
  const pattern2 = [2, 1, 2, 3, 2, 4, 2, 5];
  const pattern3 = [3, 3, 1, 1, 2, 2, 4, 4, 5, 5];
  const allPatterns = [pattern1, pattern2, pattern3];
  const lenOfAnswers = answers.length;
  let arrForCompare = [];

  allPatterns.forEach((pattern) => {
    const lenOfPattern = pattern.length;
    const remainder = lenOfAnswers % lenOfPattern;
    const numOfMatch = Math.floor(lenOfAnswers / lenOfPattern);
    let temp = [];

    for (let i = 0; i < numOfMatch; i++) {
      temp = [...temp, ...pattern];
    }

    const subPattern = pattern.slice(-remainder);
    temp = [...temp, ...subPattern];
    arrForCompare.push(temp);
  });

  let winners = [];
  let maxCnt = 0;

  arrForCompare.forEach((pattern, i) => {
    const studentNumber = i + 1;
    let cnt = 0;

    pattern.forEach((e, j) => {
      if (e === answers[j]) cnt++;
    });

    if (cnt >= maxCnt) {
      winners.push(studentNumber);
      maxCnt = cnt;
    }
  });

  return winners;
}

result = solution([1, 3, 2, 4, 2]);
console.log(result);

문제

각각의 학생이 정답을 몇 개 맞혔는지는 제대로 구했다. 그러나 문제를 가장 많이 맞힌 학생을 구할 때 문제가 생겼다. cnt가 maxCnt보다 높거나 같다면 현재 studentNumber를 winners 마지막에 추가하고, maxCnt를 현재 cnt 값으로 바꾸는 방식을 사용했으나, 현재 cnt가 maxCnt보다 높다면 winners의 모든 요소를 삭제하고 현재 요소만 들어가야 한다는 점을 간과했다.

두 번째 제출 코드

function solution(answers) {
  const pattern1 = [1, 2, 3, 4, 5];
  const pattern2 = [2, 1, 2, 3, 2, 4, 2, 5];
  const pattern3 = [3, 3, 1, 1, 2, 2, 4, 4, 5, 5];
  const allPatterns = [pattern1, pattern2, pattern3];
  const lenOfAnswers = answers.length;
  let arrForCompare = [];

  allPatterns.forEach((pattern) => {
    const lenOfPattern = pattern.length;
    const remainder = lenOfAnswers % lenOfPattern;
    const numOfMatch = Math.floor(lenOfAnswers / lenOfPattern);
    let temp = [];

    for (let i = 0; i < numOfMatch; i++) {
      temp = [...temp, ...pattern];
    }

    const subPattern = pattern.slice(0, remainder);
    temp = [...temp, ...subPattern];
    arrForCompare.push(temp);
  });

  let winners = [];
  let maxCnt = 0;

  arrForCompare.forEach((pattern, i) => {
    const studentNumber = i + 1;
    let cnt = 0;

    pattern.forEach((e, j) => {
      if (e === answers[j]) cnt++;
    });

    if (cnt > maxCnt) {
      winners = [studentNumber];
      maxCnt = cnt;
    } else if (cnt === maxCnt) {
      winners.push(studentNumber);
    }
  });

  return winners;
}

수정 사항

마지막에 winners에 들어갈 학생을 구하는 코드를 수정했다. maxCnt보다 cnt가 클 때와 같을 때를 조건으로 구분했다. cnt가 maxCnt보다 크다면 winners에 있는 학생을 모두 없애고 현재 학생만 남긴다. cnt가 maxCnt와 같다면 winners에 현재 학생을 추가하기만 한다.

문제

테스트 케이스는 모두 통과했다. 그러나 문제의 요구사항에 비해 코드의 길이가 너무 길고 논리가 복잡해졌다. 특히 answers와 길이를 맞추려고 각각의 패턴을 이어붙이는 과정에서는 나머지 계산까지 따로 해야했다. 다른 사람의 풀이를 보고 모듈러 연산을 활용하면 훨씬 단순한 논리를 사용할 수 있다는 것을 깨달았다. pattern들을 answers의 길이에 맞게 이어붙이는 것이 아니라 answers에 담긴 각 아이템들의 인덱스가 pattern의 요소들을 순서대로 순환하도록 만들 수 있다. 예를 들어 index % 5 연산의 결과는 index가 증가하더라도 0에서 4까지를 계속 순환한다.

세 번째 제출 코드

function solution(answers) {
  const pattern1 = [1, 2, 3, 4, 5];
  const pattern2 = [2, 1, 2, 3, 2, 4, 2, 5];
  const pattern3 = [3, 3, 1, 1, 2, 2, 4, 4, 5, 5];
  const allPatterns = [pattern1, pattern2, pattern3];
  let winners = [];

  allPatterns.forEach((pattern) => {
    let cnt = 0;
    answers.forEach((answer, index) => {
      const currIndex = index % pattern.length;
      if (answer === pattern[currIndex]) cnt++;
    });
    winners.push(cnt);
  });

  const max = Math.max(...winners);
  const result = [];

  winners.forEach((e, index) => {
    if (e >= max) result.push(index + 1);
  });

  return result;
}

수정 사항

answers와 같은 길이의 리스트를 만들어 서로 비교하던 방식에서 모듈러 연산을 통해 인덱스가 패턴 안에서 순환하도록 만들었다.

풀이 과정

  1. 세 수포자의 문제 푸는 패턴을 배열로 만들어 놓는다.
  2. 모든 수포자의 패턴을 정답과 맞춰보기 위해 각 패턴을 allPatterns 배열에 넣는다.
  3. 각 패턴을 돌며 정답과 패턴을 맞춰본다.
  4. 정답 배열을 돌면서 패턴의 길이로 현재 인덱스를 나눈 나머지를 저장한다. 이 값은 패턴의 인덱스를 계속 순환한다.
  5. 정답일 때마다 cnt 값을 올린다.
  6. 마지막에 cnt를 별도의 리스트에 저장한다.
  7. 반복이 끝나고 가장 높은 cnt 값을 찾는다.
  8. 가장 높은 값과 같거나 큰 cnt 값의 인덱스 + 1 값을 결과 리스트에 저장한다(각 패턴의 정답 개수는 순서대로 저장되므로 인덱스 + 1을 하면 몇 번째 패턴인지 알 수 있다.).

알아야 할 것

모듈러 연산. 리스트를 나머지까지 구해가며 answers와 똑같은 길이로 만들지 않아도 모듈러 연산을 통해 패턴의 범위를 계속 돌아가도록 할 수 있음.