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

 

📑 1. 문제설명

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

입출력 예

 
 
입출력 예 설명
 

입출력 예 #1

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

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

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

---

💡 2. 접근방식

완전탐색

첫번째 학생은 1,2,3,4,5 돌아가면서 반복(5개씩)
두번째 학생은 2,1,2,3,2,4,2,5 돌아가면서 반복(8개씩)
세번째 학생은 3,3,1,1,2,2,4,4,5,5 돌아가면서 반복(10개씩)
`모듈러 연산(%)` 해주기

모듈러 연산은 배열을 순환할 때 유용하게 사용되는 연산으로 ` i % 배열의 길이`를 사용하면 i가 배열의 길이를 넘어가더라도 다시 처음으로 돌아가서 배열의 인덱스를 반복적으로 참조할 수 있다. 그래서 각 학생마다 i 를 5, 8, 10으로 나눈 나머지 값과 answer[i]를 비교하면서 일치하면 정답을 맞춘것으로 카운팅한다. 
 
맞춘 정답은 score[] 배열에 담아 주는데, 
0번 인덱스가 첫번째 학생의 점수이고 그 뒤로 두번째, 세번째 학생의 점수가 담긴다.
세 학생의 점수를 비교할 때는 Math.max 를 중첩해서 쓰면 된다. 0,1번 인덱스 안에 있는 값을 비교해서 나온 최댓값을 다시 2번 인덱스의 값과 비교해서 최댓값을 찾으면 된다. (나는 아래에서 코드 쓰다 보니 1,2번 먼저 비교하고 결과값을 0번이랑 비교해 주었다.)
 
마지막으로 최대 점수를 받은 수포자들의 번호를 넣어 줄 리스트를 생성해서 int 형 배열로 반환한 후 리턴한다.
 
원래는 int[] answer = new int[?]; 로 선언해서 바로 반환할려고 했는데 생각해보니까
배열의 길이를 모른다. 점수가 최대인 학생의 숫자를 모르기 때문이다.
그럼 배열의 길이를 찾으려고 최대 점수인 학생을 카운팅 해서 cnt에 담아 주어야 한다.
그럼 for문을 두번 돌려야 해서 복잡한 코드가 된다. 
 

---

⭐ 3. 코드

import java.util.*;

class Solution {
    public int[] solution(int[] answers) {
        int first[] = {1, 2, 3, 4, 5}; // 첫번째
        int second[] = {2, 1, 2, 3, 2, 4, 2, 5}; // 두번째
        int third[] = {3, 3, 1, 1, 2, 2, 4, 4, 5, 5}; // 세번째
        int scores[] = {0, 0, 0}; // 각 수포자들의 점수
        
        // 수포자들의 점수 계산
        for(int i = 0; i < answers.length; i++) {
            if(answers[i]==first[i%5]) {scores[0]++;}
            if(answers[i]==second[i%8]) {scores[1]++;}
            if(answers[i]==third[i%10]) {scores[2]++;}
        }
        
        // 점수의 최댓값 계신
        int max = Math.max(scores[0], Math.max(scores[1],scores[2]));
        
        // 최대 점수를 받은 수포자 담아줄 리스트 생성
        List<Integer> list = new ArrayList<>();
        for(int i = 0; i < scores.length; i++) if(max==scores[i]) list.add(i+1);
        // 리스트를 int 타입의 배열로 변환
        int[] answer = list.stream().mapToInt(Integer::intValue).toArray();
        return answer;
    }
}

 
 
틀린 부분
1. `if(answers[i]==first[i / 5])` 로 작성했는데 생각해보니 틀려서` i / 5` 대신` i % 5` 로 수정
2. `list.add(scores[i])` 대신 `list.add(i+1)`로 수정함. 이 문제는 가장 높은 점수를 받은 사람의 점수가 아닌 번호를 반환하는 것이 목적
3. `maptoInt()` 라고 잘못써서 to를 대문자 To로 수정함 `mapToInt()`
 
 
코드에서 남길 노트

// 그냥 이렇게 한 줄로 적어도 됨
if(answers[i]==first[i%5]) {scores[0]++;}
// 이것도 마찬가지
for(int i = 0; i < scores.length; i++) if(max==scores[i]) list.add(i+1);

 
리스트를 int 배열로 반환할 때 `list.stream().mapToInt(Integer::intValue).toArray();`

// 리스트를 int 타입의 배열로 변환
int[] answer = list.stream().mapToInt(Integer::intValue).toArray();

---

 
리스트 대신 answer 배열 생성해서 푸는 코드
// 비효율이라서 비추천인데 그냥 연습 겸 써 봤다. 

import java.util.*;

class Solution {
    public int[] solution(int[] answers) {
        // 각 수험자의 답안 패턴
        int[] first = {1, 2, 3, 4, 5};
        int[] second = {2, 1, 2, 3, 2, 4, 2, 5};
        int[] third = {3, 3, 1, 1, 2, 2, 4, 4, 5, 5};
        
        // 각 수험자의 점수
        int[] scores = {0, 0, 0};

        // 주어진 답안과 비교하여 점수 계산
        for (int i = 0; i < answers.length; i++) {
            if (answers[i] == first[i % 5]) {
                scores[0]++;
            }
            if (answers[i] == second[i % 8]) {
                scores[1]++;
            }
            if (answers[i] == third[i % 10]) {
                scores[2]++;
            }
        }

        // 가장 높은 점수를 구함
        int max = Math.max(scores[0], Math.max(scores[1], scores[2]));

        // 최고 점수와 같은 점수를 얻은 사람의 수를 셈
        int cnt = 0;
        for (int score : scores) {
            if (score == max) {
                cnt++;
            }
        }

        // 최고 점수와 같은 점수를 얻은 사람 번호를 answer 배열에 저장
        int[] answer = new int[cnt];
        int index = 0;
        for (int i = 0; i < scores.length; i++) {
            if (scores[i] == max) {
                answer[index++] = i + 1; // 사람 번호는 1부터 시작
            }
        }

        return answer;
    }
}

 
 

👍🏻 좋아요 제일 많이 받은 코드

import java.util.ArrayList;
class Solution {
    public int[] solution(int[] answer) {
        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<answer.length; i++) {
            if(answer[i] == a[i%a.length]) {score[0]++;}
            if(answer[i] == b[i%b.length]) {score[1]++;}
            if(answer[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.intValue()).toArray();
    }
}

 
나랑 비슷한데 차이점은 마지막에 람다식 쓴 것
`list.stream().mapToInt(i->i.intValue()).toArray();`
 
그리고 댓글 보고 stream 쓰면 시간이 많이 늘어나는 것도 알게 되었다. 
 

 

---

👍🏻 좋아요 두번재로 많이 받은 코드 (이차원 배열)

진짜 최고인듯....  이렇게 푼 사람들은 천재이신가

import java.util.*;

class Solution {
    public static int[] solution(int[] answers) {
        int[][] patterns = {
                {1, 2, 3, 4, 5},
                {2, 1, 2, 3, 2, 4, 2, 5},
                {3, 3, 1, 1, 2, 2, 4, 4, 5, 5}
        };

        int[] hit = new int[3];
        for(int i = 0; i < hit.length; i++) {
            for(int j = 0; j < answers.length; j++) {
                if(patterns[i][j % patterns[i].length] == answers[j]) hit[i]++;
            }
        }

        int max = Math.max(hit[0], Math.max(hit[1], hit[2]));
        List<Integer> list = new ArrayList<>();
        for(int i = 0; i < hit.length; i++)
            if(max == hit[i]) list.add(i + 1);

        int[] answer = new int[list.size()];
        int cnt = 0;
        for(int num : list)
            answer[cnt++] = num;
        return answer;
    }
}

 

---

객체지향적으로 푼 최석현님의 코드

와... 진짜 대단하시다
프로그래머스에서 이것도 눈에 띄여서 가져와봤다.

import java.util.*;
import java.util.function.IntPredicate;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class Solution {
    public int[] solution(int[] answers) {
        return new Students().getBestStudents(
                Arrays.stream(answers)
                        .boxed()
                        .map(Answer::new)
                        .collect(Collectors.toList()))
                .stream()
                .mapToInt(i -> i)
                .toArray();
    }

    private static class Students {
        private final List<Student> students;

        public Students() {
            this.students = new ArrayList<>();
            this.students.add(Student.of(1, Arrays.asList(1, 2, 3, 4, 5)));
            this.students.add(Student.of(2, Arrays.asList(2, 1, 2, 3, 2, 4, 2, 5)));
            this.students.add(Student.of(3, Arrays.asList(3, 3, 1, 1, 2, 2, 4, 4, 5, 5)));
        }

        public List<Integer> getBestStudents(List<Answer> answers) {
            return this.students.stream()
                    .map(student -> student.getResult(answers))
                    .collect(Collectors.collectingAndThen(Collectors.toList(), Results::new))
                    .getBestResults().stream()
                    .map(Result::getStudentId)
                    .collect(Collectors.toList());
        }
    }

    private static class Student {
        private final Integer id;
        private final List<Answer> answerPattern;

        public Student(Integer id, List<Answer> answerPattern) {
            this.id = id;
            this.answerPattern = answerPattern;
        }

        public static Student of(Integer id, List<Integer> answerPattern) {
            return new Student(id, answerPattern.stream()
                    .map(Answer::new)
                    .collect(Collectors.toList()));
        }

        public Result getResult(List<Answer> answers) {
            Long correctCount = IntStream.range(0, answers.size())
                    .filter(isCorrect(answers))
                    .count();

            return new Result(this.id, correctCount.intValue());
        }

        private IntPredicate isCorrect(List<Answer> answers) {
            return index -> {
                int patternIndex = index % answerPattern.size();
                Answer answer = answerPattern.get(patternIndex);
                Answer correctAnswer = answers.get(index);

                return answer.isCorrect(correctAnswer);
            };
        }
    }

    private static class Results {
        private final List<Result> results;

        public Results(List<Result> results) {
            this.results = results;
        }

        public List<Result> getBestResults() {
            Result bestResult = Collections.max(results);

            return results.stream()
                    .filter(result -> result.isCorrectCountEqualTo(bestResult))
                    .collect(Collectors.toList());
        }
    }

    private static class Result implements Comparable<Result> {
        private final Integer studentId;
        private final Integer correctCount;

        public Result(Integer studentId, Integer correctCount) {
            this.studentId = studentId;
            this.correctCount = correctCount;
        }

        public boolean isCorrectCountEqualTo(Result result) {
            return this.correctCount.equals(result.correctCount);
        }

        public Integer getStudentId() {
            return studentId;
        }

        @Override
        public int compareTo(Result o) {
            return this.correctCount.compareTo(o.correctCount);
        }

    }

    private static class Answer {
        private final Integer answer;

        public Answer(Integer answer) {
            this.answer = answer;
        }

        public boolean isCorrect(Answer answer) {
            return this.answer.equals(answer.answer);
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Answer answer1 = (Answer) o;
            return Objects.equals(answer, answer1.answer);
        }

        @Override
        public int hashCode() {
            return Objects.hash(answer);
        }
    }
}

---

👉🏻 4. 같은 유형 문제(완전탐색)

[프로그래머스] (Java) 최소 직사각형 문제풀이 (완전탐색)