[알고리즘 문제 풀이] 프로그래머스 - 모의고사

문제 원본 링크: https://programmers.co.kr/learn/courses/30/lessons/42840?language=java

카테고리: 완전탐색

 

문제 설명

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

입출력 예

int[] answers = {1,2,3,4,5}; // return = {1};
int[] answers = {1,3,2,4,2}; // return = {1,2,3}

 

풀이 과정

각 수포자의 찍기 패턴을 각 정수배열 one, two, three에 담아서 answers의 값들을 비교하기로 했다. 그리고 각 수포자들이 맞춘 문제의 수는 정수 배열 answersOfStudens에 담는다. 이렇게 하면 각 수포자들이 몇개의 문제를 맞췄는지 알 수 있는 로직을 간단하게 작성할 수 있다. 그런데 문제는 문제를 가장 많이 맞힌 수포자만 찾아야 한다. 그리고 문제를 가장 많이 맞힌 수포자가 2명 이상이라면 모두 배열에 담아서 리턴해야 한다. 이부분을 나는 조금 복잡하게 생각했다. 그리고 총 여섯 번의 시도 끝에 성공시켰다. 알고보니 배열의 위치를 찾는 부분에서 -1을 하지 않는 에러가 있었다. 이것 때문에 다섯 번째 시도에서 13개 테스트 케이스 중에 3개가 통과를 못했다.

 

문제를 가장 많이 맞힌 수포자를 리스트 bestStudents에 저장하고 마지막에 int 배열로 바꿔서 리턴하면 된다. 오름차순으로 배열에 값을 저장해야하기때문에 따로 정렬을 하지 않기위해서 수포자1부터 3까지 차례로 넣을지 말지를 판단해서 list에 넣어주기로 했다. 각 수포자의 정답수가 가장 많으면 list에 넣는데, 이전에 저장된 수포자보다 많으면 list.clear()를 해서 비워준 후에 넣어주고, 기존 수포자의 정답수와 같다면 그냥 넣어준다.

 

자바 코드

    public int[] solution(int[] answers) {
        int[] one =   {1, 2, 3, 4, 5,}; // 수포자1 찍기 패턴, size = 5
        int[] two =   {2, 1, 2, 3, 2, 4, 2, 5}; // 수포자2 찍기 패턴, size = 8
        int[] three = {3, 3, 1, 1, 2, 2, 4, 4, 5, 5}; // 수포자3 찍기 패턴, size = 10
        int[] answersOfStudents = {0, 0, 0}; // 수포자들(1,2,3)이 정답을 맞힌 개수
        List<Integer> bestStudents = new ArrayList<>();

        for (int i = 0; i < answers.length; i++) {
            if (answers[i] == one[i % one.length]) answersOfStudents[0]++;
            if (answers[i] == two[i % two.length]) answersOfStudents[1]++;
            if (answers[i] == three[i % three.length]) answersOfStudents[2]++;
        }

        if (answersOfStudents[0] > 0) bestStudents.add(1);

        if (answersOfStudents[1] >= answersOfStudents[0]) {
            if (answersOfStudents[1] > answersOfStudents[0]) bestStudents.clear();
            bestStudents.add(2);
        }

        if (answersOfStudents[2] >= answersOfStudents[0] && answersOfStudents[2] >= answersOfStudents[1]) {
            if (!bestStudents.isEmpty() && answersOfStudents[2] > answersOfStudents[bestStudents.get(0) - 1])
                bestStudents.clear();
            bestStudents.add(3);
        }

        return bestStudents.stream().mapToInt(i -> i).toArray();
    }

 

 

다른 사람의 코드

가장 추천을 많이 받은 사람의 코드를 보니 for문 이후의 로직이 훨씬 간결했다. Math.mas()함수를 사용했는데, 왜 나는 이 생각을 못했을까.

    public int[] solution2(int[] answers) {
        int[] a = {1, 2, 3, 4, 5};
        int[] b = {2, 1, 2, 3, 2, 4, 2, 5};
        int[] c = {3, 3, 1, 1, 2, 2, 4, 4, 5, 5};
        int[] score = new int[3];
        for(int i=0; i<answers.length; i++) {
            if(answers[i] == a[i%a.length]) {score[0]++;}
            if(answers[i] == b[i%b.length]) {score[1]++;}
            if(answers[i] == c[i%c.length]) {score[2]++;}
        }
        int maxScore = Math.max(score[0], Math.max(score[1], score[2]));
        ArrayList<Integer> list = new ArrayList<>();
        if(maxScore == score[0]) {list.add(1);}
        if(maxScore == score[1]) {list.add(2);}
        if(maxScore == score[2]) {list.add(3);}
        return list.stream().mapToInt(i-> i).toArray();
    }

 

참고:

- 깃허브 소스 코드: 링크