[알고리즘] 모의고사

● 문제 설명

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

● 입출력 예

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

● 입출력 예 설명

입출력 예 #1

• 수포자 1은 모든 문제를 맞혔습니다.
• 수포자 2는 모든 문제를 틀렸습니다.
• 수포자 3은 모든 문제를 틀렸습니다.

따라서 가장 문제를 많이 맞힌 사람은 수포자 1입니다.

입출력 예 #2

• 모든 사람이 2문제씩을 맞췄습니다.

 

---

 

● Solution.java

import java.util.List;
import java.util.ArrayList;
import java.util.Collections;

class Solution {
	public class Student
	{
		public int number;
		public int grade;
		public List<Integer> pattern; 
		public Student (int _number, int[] _pattern)
		{
			number = _number;
			grade  = 0;
			pattern = new ArrayList<Integer>();
			
			for(int index = 0 ; index < _pattern.length ; index++)
			{
				pattern.add(_pattern[index]);
			}
		}
	}
	
	
    public int[] solution(int[] answers) {
    	int[] answer ;
        ArrayList<Integer> result = new ArrayList<Integer>();
        List<Student> students = new ArrayList<Student>();

        //수포자들의 정답 패턴 Initializing
        sutdentInit(students);
        
        int maxGrade = 0;
        
        // 정답 인덱스 완전 탐색 반복문
        for( int index = 0 ; index < answers.length ; index++ )
        {
        	// 각 정답 수포자들의 정답과 같은지 체크
        	for( int stdtIndex = 0 ; stdtIndex < 3 ; stdtIndex++ )
        	{	
        		// 정답을 맞춘 수포자들의 점수 증가
        		if( students.get(stdtIndex).pattern.get( index % students.get(stdtIndex).pattern.size() ) == answers[index] )
        			students.get(stdtIndex).grade++;
        		
        		if(students.get(stdtIndex).grade > maxGrade)
        		{
        			maxGrade = students.get(stdtIndex).grade;
        		}
        	}
        }
        
        
        for(int index = 0 ; index < students.size() ; index++)
        {
        	//최대 점수가 아닌 학생은 제외
        	if(students.get(index).grade != maxGrade )
        	{
        		students.remove(index);
        		index--;
        	}
        }


        for(int index = 0 ; index < students.size()-1 ; index++)
        {     	
        	if(students.get(index).number > students.get(index+1).number )
        	{
               Collections.swap(students, index, index+1);
        	}
        }
        
        // 결과 도출 
        answer = new int[students.size()];
        
        for(int index = 0 ; index < answer.length  ; index++ ) {
        	answer[index] = students.get(index).number;
        }
        return answer;
        
    }
    
    
    public void sutdentInit (List<Student> students)
    {
    	students.add( new Student(1, new int[]{1,2,3,4,5} ));
    	students.add( new Student(2, new int[]{2,1,2,3,2,4,2,5} ));
    	students.add( new Student(3, new int[]{3,3,1,1,2,2,4,4,5,5}));
    }
}