[99클럽 코테 스터디] 15일차 TIL - 모의고사

오늘의 학습 키워드

</> 완전탐색

공부한 내용 본인의 언어로 정리하기

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

class Solution {
    public int[] solution(int[] answers) {
    
        //수포자1,2,3의 반복된 답안 배열
        int[] one = {1,2,3,4,5};
        int[] two = {2,1,2,3,2,4,2,5};
        int[] three = {3,3,1,1,2,2,4,4,5,5};
        
        //수포자의 정답 수
        int oneCount = 0;
        int twoCount = 0;
        int threeCount = 0;
        
        //정답 답안과 수포자의 답안이 일치할 경우 정답수++
        for(int i = 0; i<answers.length;i++){
            if(answers[i] == one[i % one.length]){
                oneCount++;
            }
            if(answers[i] == two[i % two.length]){
                twoCount++;
            }
            if(answers[i] == three[i % three.length]){
                threeCount++;
            }
        }
        
        //최고 득점자 리스트             
        List<Integer> topScorers = new ArrayList<>();  
        
        //최대 획득 점수 분류 (Math.max를 이용해서 최대값을 추출)
        int maxCount = Math.max(oneCount, Math.max(twoCount, threeCount));
        
        //최고 점수가 각 수포자의 정답수와 일치하면 해당 인원 추가
        if(maxCount == oneCount){
            topScorers.add(1);
        }
        if(maxCount == twoCount){
            topScorers.add(2);
        }
        if(maxCount == threeCount){
            topScorers.add(3);
        }
        
        //리스트를 Int배열로 변환후 반환
		return topScorers.stream().mapToInt(Integer::intValue).toArray();
	}
}

오늘의 회고

오늘 주제는 완전탐색이라고 한다. 하루하루 문제가 새로 나올수록 내가 정말 모르는게 많구나라고 더 느낀다.
완전 탐색에는 단순 반복문( Simple Iteration ), 재귀 함수( Recursion ), 비트마스크( Bitmask ), 순열( Permutation ), 조합( Combination ), 백트래킹( Backtracking ), 깊이 우선 탐색( DFS ), 너비 우선 탐색( BFS ), Meets in the Middle( MITM )이 있다.

1. 단순 반복문: 하나 이상의 반복문을 사용하여 모든 가능한 경우를 순차적으로 탐색한다.
2. 재귀 함수: 함수가 자기 자신을 호출아며 모든 경우를 탐색
3. 비트마스크: 정수의 이진수 표현을 활용하여 부분 집합을 표현하고 탐색
4. 순열: 주어진 수열의 모든 가능한 순서를 탐색
5. 조합: 주어진 집합에서 특정 개수의 원소를 선택하는 모든 경우를 탐색
6. 백트래킹: 해답를 찾는 도중 해답이 아니어서 막히면, 되돌아가서 다시 다른 경로로 해답을 찾아가는 기법
7. 깊이 우선 탐색: 그래프나 트리에서 가능한 모든 경로를 탐색할 때 사용
8. 너비 우선 탐색: 그래프나 트리에서 모든 인접 노드를 우선적으로 탐색
9. Meet in the Middle: 문제를 두 부분으로 나누어 각각 완전 탐색한 후, 결과를 합치는 방식

오늘은 그 중에서 가장 한눈에 들어온 단순 반복문을 이용하여 문제를 풀었다.

오늘 문제의 과정은 수포자 3명이 각각 반복적인 숫자로 답안을 찍었고 그 중에서 가장 많이 문제를 맞춘 사람을 골라내는 문제였다.

시작은 직접 그 배열을 만들어 주는 것이었고 정답을 얼마나 맞췄는지 찾아내기 위해 각각 수포자들의 카운트를 만들어 주었다.

//수포자1,2,3의 반복된 답안 배열
int[] one = {1,2,3,4,5};
int[] two = {2,1,2,3,2,4,2,5};
int[] three = {3,3,1,1,2,2,4,4,5,5};

//수포자의 정답 수
int oneCount = 0;
int twoCount = 0;
int threeCount = 0;

그리고 정답 답안의 길이만큼 반복하여 정답의 index의 값과 찍은 index의 값이 같으면 각 수포자들의 카운트 수를 증가시켜 주었다.

//정답 답안과 수포자의 답안이 일치할 경우 정답수++
for(int i = 0; i<answers.length;i++){
	if(answers[i] == one[i % one.length]){
		oneCount++;
	}
	if(answers[i] == two[i % two.length]){
		twoCount++;
	}
	if(answers[i] == three[i % three.length]){
		threeCount++;
	}
}

어떻게 비교를 하면 좋을까 생각하다 각 수포자들이 찍은 답의 반복되는 길이가 달라 그 답안들의 최대 길이를 나누면 각 답안들의 갯수마다 반복되어 값이 일정하게 비교가 된다고 생각해 진행했다.

정답 수를 도출해내었으니 이제 최고 득점자와 최대 점수를 얻어야했다.

//최고 득점자 리스트             
List<Integer> topScorers = new ArrayList<>();  
        
//최대 획득 점수 분류 (Math.max를 이용해서 최대값을 추출)
int maxCount = Math.max(oneCount, Math.max(twoCount, threeCount));

추출해낸 최대 획득 점수가 각 수포자가 맞춘 정답수와 일치한다면 최고 득점자 리스트에 추가해주었다.

//최고 점수가 각 수포자의 정답수와 일치하면 해당 인원 추가
if(maxCount == oneCount){
topScorers.add(1);
}
if(maxCount == twoCount){
topScorers.add(2);
}
if(maxCount == threeCount){
topScorers.add(3);
}

이번에도 리스트를 그대로 반환하려다 오류가 나서 리스트를 정수 배열로 변환하는 법을 검색해서 만들었다.
여러가지 방법이 있었지만 람다식으로 만드는 변환식보다 내가 사용한 변환식이 더 직관적이고 좋아 보여서 사용하게 되었다.

//리스트를 Int배열로 변환후 반환
topScorers.stream().mapToInt(Integer::intValue).toArray();
}

AI 코드리뷰

현재 코드의 장점

1. 간단하고 이해하기 쉬운 구조
2. 각 수포자의 답안 패턴을 배열로 효과적으로 표현
3. 모듈로 연산을 통해 패턴 반복 처리

현재 코드의 단점

1. answers 배열을 여러 번 순회하여 약간의 비효율성 존재
2. ArrayList를 사용하여 불필요한 객체 생성 발생

시간 복잡도

O(n), 여기서 n은 answers 배열의 길이입니다.

개선된 코드 제안

import java.util.Arrays;

class Solution {
    public 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[] scores = new int[3];
        
        for (int i = 0; i < answers.length; i++) {
            for (int j = 0; j < 3; j++) {
                if (answers[i] == patterns[j][i % patterns[j].length]) {
                    scores[j]++;
                }
            }
        }
        
        int maxScore = Math.max(scores[0], Math.max(scores[1], scores[2]));
        
        return IntStream.range(0, 3)
                        .filter(i -> scores[i] == maxScore)
                        .map(i -> i + 1)
                        .toArray();
    }
}

개선된 버전의 장점:

1. 단일 루프로 모든 수포자의 점수를 계산하여 효율성 향상
2. 2D 배열을 사용하여 패턴 관리를 더욱 체계적으로 수행
3. Stream API를 사용하여 결과 생성 로직을 간결하게 표현

개선된 버전의 단점:
1. 원래 코드보다 약간 더 복잡한 구조
2. Stream API 사용으로 인해 매우 큰 입력에 대해서는 약간의 성능 저하 가능성

시간 복잡도: 여전히 O(n) 이지만, 상수 인자가 줄어들어 실제 실행 시간은 개선됩니다.
이 개선된 버전은 여전히 완전 탐색 방식을 사용하지만, 단일 패스로 모든 계산을 수행하여 효율성을 높였습니다.

---

내일 공부할 것 :

1. Java Stream API: 코드에서 사용된 IntStream에 대해 더 자세히 학습하세요. 이는 함수형 프로그래밍 스타일을 Java에 도입한 강력한 도구입니다.

2. 다차원 배열: 2D 배열을 사용하여 코드를 더욱 구조화하는 방법에 대해 학습하세요.

3. 시간 복잡도와 공간 복잡도: 알고리즘의 효율성을 분석하는 이 개념들에 대해 더 깊이 이해하세요.

4. 다양한 완전 탐색 기법: 이전에 제공한 완전 탐색의 다른 방법들(예: 백트래킹, DFS, BFS 등)에 대해 학습하고 언제 어떤 방법을 사용하는 것이 좋을지 고민해보세요.

문제

https://school.programmers.co.kr/learn/courses/30/lessons/42840