[프로그래머스] 완전탐색 - 모의고사 문제 풀이

오늘은 프로그래머스에서 완전탐색 알고리즘 중 "모의고사" 문제 풀이를 해보겠습니다. 완전탐색은 무식해 보일정도로 모두 탐색해서 결과를 얻어야하는 알고리즘 방법입니다. 이 문제처럼 어떤 문제를 풀 때 하나하나 다 확인해서 결과를 도출해야할 경우도 있으니 유사한 문제를 풀 때 참고하시기 바랍니다. 그럼 프로그래머스의 모의고사 문제 풀이 시작해보겠습니다.

 

 

 

 

프로그래머스 > 완전탐색 > 모의고사 문제 풀이

 

 

 

 

▷ 문제 정보

• 문제명: 모의고사
• 문제 난이도: Level 1
• 문제 푼 사람수: 47720명
• 사용 가능 언어: 11개 (JavaScript 사용)

 

 

 

 

▷ 문제 설명

수포자는 수학을 포기한 사람의 준말입니다. 수포자 삼인방은 모의고사에 수학 문제를 전부 찍으려 합니다. 수포자는 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 함수를 작성해주세요.

 

 

문제를 이해하기 쉽게 간단하게 정리해보도록 하겠습니다.

 

• 수학을 포기한 학생들 3명은 모의고사 수학 문제를 아래와 같이 순서대로 찍는다.
  • 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 ...]
• 문제의 정답(answers)이 주어졌을 때, 가장 많은 문제를 맞힌 사람을 배열로 반환한다.

 

 

 

 

▷ 제한 조건

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

 

위 문제의 제한 조건을 정리해보겠습니다.

• answers 배열의 최대 길이는 10,000이다.
• answers의 각 항목은 1, 2, 3, 4, 5 중 하나이다.
• return 값은 오름차순으로 입력한다.

 

 

 

 

▷ 입출력 예

answers	return
[1, 2, 3, 4, 5]	[1]
[1, 3, 2, 4, 2]	[1, 2, 3]

 

 

 

 

▷ 입출력 예 설명

입출력 예 #1
  · 수포자 1은 모든 문제를 맞혔습니다.
  · 수포자 2는 모든 문제를 틀렸습니다.
  · 수포자 3은 모든 문제를 틀렸습니다.
따라서 가장 문제를 많이 맞힌 사람은 수포자 1입니다.

입출력 예 #2
  · 모든 사람이 2문제씩을 맞췄습니다.

 

 

 

 

▷ 알고리즘 만들기

이번 모의고사 문제의 알고리즘은 1, 2, 3번 수포자 학생의 답안과 일일히 비교하여 제일 많이 맞춘 사람의 리스트를 결과로 반환하는 것이 키 포인트입니다.

 

1. 수포자 학생들의 답안 리스트 및 정답 수 리스트를 변수화한다.
2. 문제의 정답(answers)와 수포자 학생들의 답안 리스트와 비교하여 각 학생 별 정답 수를 계산한다.
3. 가장 많이 맞춘 정답 수를 확인한다.
4. 가장 많이 맞춘 정답 수와 같은 개수를 맞춘 학생의 리스트를 반환한다.

 

이 문제의 알고리즘은 정말 간단합니다. 하지만 이 알고리즘을 구현하고 시간복잡도를 계산할 때 최선의 코드로 구현하는 것이 포인트일 것입니다.

 

 

 

 

▷ 코드 구현

function solution(answers) {
	// 1. 수포자 학생들의 답안 리스트와 정답 수 리스트를 변수화한다.
    const answerPattern = [[1,2,3,4,5], [2,1,2,3,2,4,2,5], [3,3,1,1,2,2,4,4,5,5]];
    const answerMatch = [0, 0, 0];
    
    // 2. 문제의 정답(answers)와 수포자 학생들의 답안 리스트와 비교하여 각 학생 별 정답 수를 계산한다.
    for(let i = 0; i < answers.length; i++) {
        for(let j = 0; j < answerPattern.length; j++) {
            if(answerPattern[j][i % answerPattern[j].length] == answers[i]) {
                answerMatch[j]++;
            }
        }
    }
    
    // 3. 가장 많이 맞춘 정답 수를 확인한다.
    const maxAnswerCount = answerMatch.reduce((prev, cur) => {
        return prev < cur ? cur : prev;        
    }, 0);
    
    // 4. 가장 많이 맞춘 정답 수와 같은 개수를 맞춘 학생의 리스트를 반환한다.
    const result = answerMatch.reduce((prev, cur, index) => {
        if(maxAnswerCount === cur) {
            prev.push(index+1);
        }
        return prev;
    }, []);
    
    return result;
}

 

 

위 알고리즘을 풀어서 코드로 구현해보았습니다. 

 

 

 

 

코드의 결과는 아래 처럼 14개의 정확성 테스트 케이스 결과 모두 통과하여 만점을 받았습니다. 알고리즘 문제를 하나하나 풀어감에 있어 성취감과 만족감을 키울 수 있었습니다. 여러분도 제 풀이를 참고하셔도 좋지만, 참고하기 전에 단계 별로 어떻게 문제를 풀어나가는지를 보고 따라하면서 자기 만의 알고리즘 문제 풀이 방법으로 습득하시면서 개발자로 발돋움하실 수 있는 경험을 해보시길 바랍니다.