99클럽 코테 스터디 15일차 TIL (완전탐색)

문제

---

문제 해결

1. 정답 배열이 주어지면 각 수포자 학생들의 정답과 비교하여 점수를 낸다.

2. 점수배열에는 순서대로 1~3번 학생까지의 점수가 담겨져 있다.

3. 최대값을 추려내고 최대값을 가진 학생들을 List에 담는다.

나의 풀이 (개선 전)

class Solution {
    public int[] solution(int[] answers) {
        int[] student1 = {1, 2, 3, 4, 5, 1, 2, 3, 4, 5};
        int[] student2 = {2, 1, 2, 3, 2, 4, 2, 5};
        int[] student3 = {3, 3, 1, 1, 2, 2, 4, 4, 5, 5};
        int[] cnt = new int[3];

        for(int i = 0; i < answers.length; i++){
            if(answers[i] == student1[i % student1.length]){
                cnt[0]++;
            }

            if(answers[i] == student2[i % student2.length]){
                cnt[1]++;
            }

            if(answers[i] == student3[i % student3.length]){
                cnt[2]++;
            }
        }

        int maxScore = Math.max(cnt[0], Math.max(cnt[1], cnt[2]));
        List<Integer> results = new ArrayList<>();
        for(int i = 0; i < 3; i++){
            if(maxScore == cnt[i]){
                results.add(i + 1);
            }
        }

        return results.stream().mapToInt(Integer::intValue).toArray();
    }
}

 

나의 풀이 (개선 후)

class Solution {
    private final 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}
    };

    public int[] solution(int[] answers) {
        int[] cnt = new int[3];

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

        int maxScore = Math.max(cnt[0], Math.max(cnt[1], cnt[2]));
	List<Integer> results = new ArrayList<>();
        for(int i = 0; i < 3; i++){
            if(maxScore == cnt[i]){
                results.add(i + 1);
            }
        }

        return results.stream().mapToInt(Integer::intValue).toArray();
    }
}

int[] 배열을 각자 따로 선언한 것과 for문 내부 비슷한 if문 대한 피드백을 받았다.
따로 작성한 이유는,
제한 조건이 10^4이라 n^2이 되어버리면 시간초과 발생 이슈 때문이였고 for문 하나로 해결하려했다.

하지만, 이중 루프를 통해 O(n * m)으로 보일 수 있지만
학생은 고정으로 3명밖에 없어서 실질적으로 O(n)인 것이였다......!!

그리고 1,2,3번 학생 모두 찍은 답안들이 반복패턴을 보인다는 것을 알았다.
i % patterns[j].length 나머지연산을 사용해서 본인 답안을 반복되게 했다

---

회고

• 이중루프 == n^2 라는 고정관념 버리자
• 개선 전과 개선 후는 성능상 차이는 크게 없지만 하나의 습관을 만드는 것이다.
  - 역할이 크게 다르지 않다면 비슷해 보이는 코드 && 비슷한 역할을 하는 코드는 되도록 하나로 만들자.