[99클럽 코테 스터디] 36일차 TIL - 적어도 대부분의 배수

Hoxy?·2024년 8월 26일

99클럽 TIL 개발자취업 코딩테스트준비 항해99

99클럽 코테 스터디

목록 보기

36/42

오늘의 학습 키워드

</> 완전 탐색

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

import java.util.*;
public class Main {
     public static void main(String[] args) {
         Scanner sc = new Scanner(System.in);
         int[] arr = new int[5];
         int count = 0;
         int result = 0;
         
         for(int i = 0; i < 5; i++){
             arr[i] = sc.nextInt();
         }
         
         while(true){
             //1부터 시작
             result++;
             count = 0;
             for(int i = 0; i < 5; i++){
                 if(result >= arr[i] && result % arr[i] == 0){
                     count++;
                 }
             }
             if(count > 2){
                 break;
             }
         }
         System.out.print(result);
     }
}

오늘의 회고

오늘 문제는 완전탐색(Brute Force)문제이며 서로 다른 다섯 개의 자연수가 주어질 때, 적어도 배부분의 배수를 출력하는 프로그램을 작성하는 것이다.
여기서 번역을 개떡같이 해놓아서 처음에 무슨 말인가 싶었다. "적어도 대부분의 배수를 출력"이라는 말은 입력되는 수가 5이니 입력되는 예제의 3개 이상의 최소 공배수를 구하라는 말이다.

오늘도 백준 문제였기 때문에 예제 입력을 Scanner로 받아오도록 했다. 물론 BufferedReader도 있고 StringTokenizer도 있지만 그냥 Scanner로 쓰고 빨리 끝내고 싶었다.

주어지는 예제가 5개 이므로 입력값들을 저장해줄 배열 arr의 크기를 5로 제한해주고 몇개의 입력값이 나누어 떨어지는지 체크해 줄 변수 count와 결과값을 저장할 변수를 초기화 해주었다.

 int[] arr = new int[5];
         int count = 0;
         int result = 0;

그리고 예제를 입력한 배열을 만들어준다.

for(int i = 0; i < 5; i++){
	arr[i] = sc.nextInt();
}

이제 예제와 필요한 값들을 만드는 과정은 끝이 났다.

이제 핵심인 완전탐색으로 조건을 만족하는 값을 구해내어야한다. 몇에서 3개 이상이 나눠질지 모르기 때문에 3개 이상 나눠질때 까지 무한루프 시켜준다. 조건은 예제 5개의 값을 모두 비교를 해주는데 3개 이상 나눠지지 않으면 count를 0으로 초기화 해주면서 계속 반복해준다.

while(true){
	result++;
    count = 0;
    for(int i = 0; i < 5; i++){
    	if(result >= arr[i] && result % arr[i] == 0){
        	count++;
        }
    }
    if(count > 2){
    	break;
    }
}

모든 과정이 끝났으므로 result를 출력해주면 성공이다.

System.out.print(result);

AI 코드리뷰

현재 코드의 장점

문제 해결 방식: 입력된 다섯 개의 숫자 중 세 개 이상의 숫자로 나누어떨어지는 가장 작은 수를 찾기 위한 루프 구조가 잘 설계되었습니다.
단순한 논리: 코드의 논리가 단순하며, 누구나 쉽게 이해할 수 있습니다.
배열 사용: 배열을 사용해 입력된 숫자들을 저장한 후 루프에서 배열을 순회하는 방식은 적절합니다.

현재 코드의 단점

비효율성: 작은 숫자에 대해서는 빠르게 결과를 찾을 수 있지만, 입력된 숫자가 크면 루프가 오래 걸릴 수 있습니다. 예를 들어, 배열의 요소가 모두 큰 소수인 경우, 결과를 찾기 위해 매우 큰 수까지 계산해야 합니다.
입력 제약: 코드가 다섯 개의 숫자에 고정되어 있습니다. 만약 더 많은 숫자에 대해 같은 작업을 해야 한다면, 코드 변경이 필요합니다.
고정된 크기: 배열의 크기가 고정되어 있어 유연성이 떨어집니다. 배열의 크기를 변수로 두면 더 일반적인 상황에서도 사용할 수 있습니다.

시간 복잡도

시간 복잡도: O(result * 5) (where result는 3개 이상의 배열 요소로 나누어떨어지는 가장 작은 수)
result의 최대 값에 따라 시간이 증가할 수 있기 때문에 최악의 경우에는 매우 큰 시간이 소요될 수 있습니다.

개선된 코드 제안

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int[] arr = new int[5];
        int result = 1;
        
        for (int i = 0; i < 5; i++) {
            arr[i] = sc.nextInt();
        }
        
        // 오름차순 정렬
        Arrays.sort(arr);
        
        while (true) {
            int count = 0;
            for (int i = 0; i < 5; i++) {
                if (result % arr[i] == 0) {
                    count++;
                }
            }
            if (count >= 3) {
                break;
            }
            result++;
        }
        System.out.print(result);
    }
}

현재 코드의 장점

정렬: 배열을 정렬함으로써 더 작은 값부터 나누어보는 것이 가능해졌습니다. 이로 인해 불필요한 연산을 줄일 수 있습니다.
코드 개선: 코드를 조금 더 간결하게 만들었으며, count 변수를 루프 내에서 초기화함으로써 가독성을 향상시켰습니다.
유연성: 여전히 다섯 개의 숫자에 고정되어 있지만, 배열 크기를 쉽게 변경할 수 있습니다. 단, 이 점은 개선 전 코드와 동일한 부분입니다.

현재 코드의 단점

근본적인 비효율성 해결 부족: 여전히 큰 숫자에 대해서는 성능이 떨어질 수 있습니다. 예를 들어, 주어진 숫자들이 매우 큰 경우 result 값이 매우 크게 증가할 때까지 루프가 계속됩니다.
복잡성 증가: 정렬을 사용하면서 약간의 오버헤드가 발생합니다. 하지만 이는 입력된 배열의 크기가 매우 작기 때문에 거의 무시할 수 있습니다.

시간 복잡도