essential
essential

4. trialExamination

패턴과 일치 불일치 확인

algorithm test

04. trialExamination

Sunhyup Lee. (2024). To be a successful candidate for the coding test. goldenrabbit. p.117.


Problem solving

수포자의 패턴과 정답이 얼마나 일치하는지 확인하는 절차와 가장 높은 점수를 저장하는 배열 형성


① The first way to solve the problem : for문 이용해서 풀기

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 scores = [0, 0, 0];

  for (const [i, answer] of answers.entries()) {
    for (const [j, pattern] of patterns.entries()) {
      if (answer === pattern[i % pattern.length]) {
        scores[j] += 1;
      }
    }
  }
  const maxScore = Math.max(...scores);

  const highestScore = [];
  for (let i = 0; i < scores.length; i++) {
    if (scores[i] === maxScore) {
      highestScore.push(i + 1);
    }
  }
  return highestScore;
}

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

🧐 시간복잡도는 어떨까?

[Done] exited with code=0 in 0.069 seconds

1) 패턴과 정답을 비교하는 부분: O(n)

최종 시간 복잡도: O(n)



② The second way to solve the problem : map과 filter를 사용한 풀이

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 scores = patterns.map(pattern =>
    answers.reduce((score, answer, idx) =>
      answer === pattern[idx % pattern.length] ? score + 1 : score, 0)
  );

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

  // 최고 점수를 받은 사람들의 번호를 구함
  return scores
    .map((score, idx) => score === maxScore ? idx + 1 : null)
    .filter(v => v !== null);
}

🧐 시간복잡도는 어떨까?

[Done] exited with code=0 in 0.068 seconds

1) patterns.map()의 시간 복잡도: O(n)
2) Math.max() 및 그 이후의 처리: O(1) 소요

최종 시간 복잡도: O(n)



③ The third way to solve the problem : 점수 계산과 비교를 한 번에 처리하는 방식

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 scores = [0, 0, 0];
  let maxScore = 0;
  const highestScore = [];

  answers.forEach((answer, i) => {
    patterns.forEach((pattern, j) => {
      if (answer === pattern[i % pattern.length]) {
        scores[j]++;
        // 현재 점수가 최고 점수보다 크면 최고 점수를 갱신하고 배열을 초기화
        if (scores[j] > maxScore) {
          maxScore = scores[j];
          highestScore.length = 0; // 배열 초기화
          highestScore.push(j + 1); // 새로운 최고 점수를 가진 사람 추가
        } else if (scores[j] === maxScore) {
          highestScore.push(j + 1); // 최고 점수와 같은 경우 추가
        }
      }
    });
  });

  return highestScore;
}

🧐 시간복잡도는 어떨까?

[Done] exited with code=0 in 0.067 seconds

1) forEach 루프는 N번 반복: O(n)

최종 시간 복잡도: O(n)



Development
Algorithm