[프로그래머스] 모의고사 (JavaScript)

알고리즘 문제풀이 [프로그래머스] 모의고사 (JavaScript)

프로그래머스 Level 1 - 모의고사

• 문제 분류: 완전탐색
• 문제 출처: 프로그래머스 Level 1 - 모의고사
• 라벨: Level 1, JavaScript

문제

• 입력: 모의고사 정답이 순서대로 담긴 배열 answers

• 출력: 정답을 가장 많이 맞춘 사람의 번호를 배열에 담아 리턴(오름차순으로 정렬할 것)

• 1번 수포자가 정답을 찍는 방식: 1, 2, 3, 4, 5, …(반복)
• 2번 수포자가 정답을 찍는 방식: 2, 1, 2, 3, 2, 4, 2, 5, …(반복)
• 3번 수포자가 정답을 찍는 방식: 3, 3, 1, 1, 2, 2, 4, 4, 5, 5, …(반복)

풀이1

• 문제수에 맞춰 1,2,3번 수포자의 정답지를 담은 배열을 확장한다.(extendArr()함수) (문제수 > 수포자의 답인 경우를 대비하기 위해 배열을 확장하는 것이다.)
• 정답이 담긴 배열을 돌면서 수포자 1,2,3의 정답지와 비교해 사람마다 정답을 맞춘 개수를 리턴한다. (compArr()함수)
• 가장 많이 맞춘 정답 개수를 찾아 max 변수에 저장한다. max만큼 정답을 맞춘 사람을 찾아 answer 배열에 저장한다.(가장 많이 맞힌 사람이 여러명일 수 있기 때문)
• answer 배열을 오름차순으로 정렬하고 최종적으로 리턴한다.

풀이1 코드

function extendArr(arr, len) {
  const div = len / arr.length;
  let result = [];
  if (div <= 1) {
    return arr;
  } else {
    if (len % arr.length === 0) {
      for (let i = 0; i < Math.floor(div); i++) {
        result = [...result, ...arr];
      }
    } else {
      for (let i = 0; i < Math.floor(div) + 1; i++) {
        result = [...result, ...arr];
      }
    }
    return result;
  }
}

function compArr(arr, answers) {
  // 맞춘 개수를 리턴
  let count = 0;
  for (let i = 0; i < answers.length; i++) {
    if (arr[i] === answers[i]) count++;
  }
  return count;
}

function solution(answers) {
  var answer = [];
  const obj = [];

  const one = [1, 2, 3, 4, 5];
  const two = [2, 1, 2, 3, 2, 4, 2, 5];
  const three = [3, 3, 1, 1, 2, 2, 4, 4, 5, 5];

  const new_one = extendArr(one, answers.length);
  const new_two = extendArr(two, answers.length);
  const new_three = extendArr(three, answers.length);

  obj.push({
    id: 1,
    ans_cnt: compArr(new_one, answers),
  });
  obj.push({
    id: 2,
    ans_cnt: compArr(new_two, answers),
  });
  obj.push({
    id: 3,
    ans_cnt: compArr(new_three, answers),
  });

  const max = obj.reduce((a, b) => (a.ans_cnt > b.ans_cnt ? a : b)).ans_cnt;
  const new_obj = obj.filter((elem) => elem.ans_cnt === max);
  answer = new_obj.map((elem) => elem.id);
  answer.sort((a, b) => a - b);

  return answer;
}

• 시간 복잡도: O(n)

풀이2 (풀이1 개선)

풀이1처럼 배열을 확장하지 않고 나머지 연산(%)으로 정답과 수포자들의 답을 비교할 수 있도록 수정했다.

풀이2 코드

function solution(answers) {
  let answer = [];
  const obj = [];

  const supoja1 = [1, 2, 3, 4, 5];
  const supoja2 = [2, 1, 2, 3, 2, 4, 2, 5];
  const supoja3 = [3, 3, 1, 1, 2, 2, 4, 4, 5, 5];
  let count1 = 0,
    count2 = 0,
    count3 = 0;

  for (let i = 0; i < answers.length; i++) {
    if (supoja1[i % supoja1.length] === answers[i]) count1++;
    if (supoja2[i % supoja2.length] === answers[i]) count2++;
    if (supoja3[i % supoja3.length] === answers[i]) count3++;
  }

  obj.push(
    {
      id: 1,
      ans_cnt: count1,
    },
    {
      id: 2,
      ans_cnt: count2,
    },
    {
      id: 3,
      ans_cnt: count3,
    }
  );

  const max = obj.reduce((a, b) => (a.ans_cnt > b.ans_cnt ? a : b)).ans_cnt;
  const new_obj = obj.filter((elem) => elem.ans_cnt === max);
  answer = new_obj.map((elem) => elem.id);
  answer.sort((a, b) => a - b);

  return answer;
}

// solution([1, 2, 3, 4, 5]);

• 시간 복잡도: O(n)

풀이1 보다 알고리즘 실행 시간이 개선되었다.