자세한문제내용

모의고사

수포자는 수학을 포기한 사람의 준말입니다. 수포자 삼인방은 모의고사에 수학 문제를 전부 찍으려 합니다. 수포자는 1번 문제부터 마지막 문제까지 다음과 같이 찍습니다.

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하는 값을 오름차순 정렬해주세요.

//########################### solution 1 ###########################

function solution(answers) { //조금 느렸다. answer을 filter 3번씩 해서?
   
    let person1 = [1,2,3,4,5]
    let person2 = [2,1,2,3,2,4,2,5]
    let person3 = [3,3,1,1,2,2,4,4,5,5]
    
   let gotAns1 = answers.filter((got,idx) => got === person1[idx%5]).length 
   let gotAns2 = answers.filter((got,idx) => got === person2[idx%8]).length
   let gotAns3 = answers.filter((got,idx) => got === person3[idx%10]).length
   
   let max = Math.max( gotAns1, gotAns2, gotAns3)
   let result = []
   if( gotAns1 === max){
       result.push(1)
   }
   if( gotAns2 === max){ //else if 하니까 안됬음 왜?
       result.push(2)
   }
    if(gotAns3 === max){
       result.push(3)
   }
    return result;
}

//########################### solution 2 ###########################
function solution(answers) { // 훨씬 빠름
    var answer = [];
    const man1 = [1, 2, 3, 4, 5];
    const man2 = [2, 1, 2, 3, 2, 4, 2, 5];
    const man3 = [3, 3, 1, 1, 2, 2, 4, 4, 5, 5];
    let count = [0, 0, 0];

    for(let i = 0; i < answers.length; i++) {
        if(answers[i] == man1[i % man1.length]) count[0]++; 
        if(answers[i] == man2[i % man2.length]) count[1]++;
        if(answers[i] == man3[i % man3.length]) count[2]++;
    }

    const max = Math.max(count[0], count[1], count[2]);
    for(let i = 0; i < count.length; i++) {
        if(max == count[i]) answer.push(i + 1);
    }

    return answer;
}

Point

answers.filter((got,idx) => got === person1[idx % person1.length]).length
'%' 연산자 활용하면 더작은수(idx)를 큰수(person1.length)로 나눴을때 나머지는 작은 수 그대로 남는 원리

완전 탐색이라는 키워드 때문인지, 최근에 배운 dfs,재귀를 떠올려 복잡하게 썼는데, 사실 완전 탐색의 방법에는 여러가지가 있다.

• Brute Force 기법 - 반복 / 조건문을 활용해 모두 테스트하는 방법
• 순열(Permutation) - n개의 원소 중 r개의 원소를 중복 허용 없이 나열하는 방법
• 재귀 호출 - 숫자 N개의 숫자 중 M개를 고르는 경우라고 할 때, N과 M이 매우 큰 숫자일때
• 비트마스크 - 2진수 표현 기법을 활용하는 방법
• BFS, DFS를 활용하는 방법

1번째 방법보다 2번째 방법이 속도가 빨랐다.
그래서 배열의 반복문 메서드들을 언제 사용해야 하는지 어떤 성능이 있는지 알아보았다

<배열 메서드들 성능 비교>

대략
일반 for문이 가장 빠르고, 효율적이다.
filter도 빠른편인데 대용량 배열처리시에는 메모리 overflow가능성 있다.(map도 비슷)
reduce는 활용도가 높다

참고블로그