프로그래머스 모의고사 자바스크립트

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/42840

프로그래머스

 

문제 풀이를 위해 생각한 것

1. 수포자1, 2, 3의 패턴을 미리 저장하고, 수포자 i의 답 배열의 길이가 answers의 길이보다 작은 동안, 수포자 i의 답 배열에 각 수포자 i에 대한 pattern원소를 추가한다.
2. 정답 배열의 길이 동안 정답 배열의 인덱스와 동일한 인덱스의 수포자 i 답 배열 원소가 서로 같은지 비교한다.
   1. 같으면 cnt++
3. 수포자 i의 정답 수와 현재 최대 정답수를 비교하여,
   1. 수포자 i의 정답 수가 더 크면 answer 배열은 [i]로 초기화
   2. 같으면 answer 배열에 수포자 i를 추가
4. 마지막으로 정답 수 최대 인원이 한 명 이상일 경우 배열을 오름차순 정렬하여 return한다.

 

사용한 자료구조 / 알고리즘

완전탐색

 

풀이 코드

function solution(answers) {
    let answer = [];
    
    const pattern = {
        '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]
    }
    
    const stud = {
        '1': [],
        '2': [],
        '3': []
    }
    
    let curMax = 0

    for (let i = 1; i <= 3; i++) {
        let cnt = 0   
        
        while (stud[i].length < answers.length) {
            pattern[i].forEach(item => {stud[i].push(item)})
        }
        
        for (let j = 0; j < answers.length; j++) {
            if (stud[i][j] == answers[j]) {
                cnt++
            }
        }
        
        if (cnt > curMax) {
            answer = [i]
            curMax = cnt
        } else if (cnt == curMax) {
            answer.push(i)
        } else {
            continue
        }
    }
    
    if(answer.length > 1) {
        answer.sort()
    }
    
    return answer;
}

 

시간 복잡도 분석

 

O(N).

3 * (학생 답 배열에 원소 추가 O(N) + answers 배열 길이 동안, 학생 답 배열 원소 비교 O(N)).

3은 상수이기에 시간 복잡도는 O(N)이다.