[백준] 10818 최소, 최대 (설명/코드/정답)

 

문제 링크 : https://www.acmicpc.net/problem/10818

 

 

	난이도		알고리즘
		브론즈3	수학, 구현

 

1. 요구 사항 이해

시간, 메모리 제한 : 1초 / 256MB

주어진 정수 중 최댓값과 최솟값을 찾는 프로그램 작성

 

 

 

2. 설계/검증 

 

복잡도

시간 복잡도	최악의 경우	공간 복잡도
O(N)		O(N)

 

입력 처리: 첫 번째 줄에서 정수 N을 입력받고, 두 번째 줄에서 N개의 정수를 입력받습니다.

입력받는 과정은 각 입력마다 O(1)의 시간이 소요되므로, N개의 정수를 입력받는 데 O(N)의 시간이 걸립니다.
최솟값과 최댓값 찾기: 배열을 한 번 순회하면서 각 요소를 비교합니다. 이 과정은 O(N)의 시간이 걸립니다.

O(N)+O(N)=O(N)  시간 복잡도는 O(n)

 

배열: 정수 N개의 입력을 저장하기 위해 크기 N인 배열을 사용합니다. 이 배열의 공간복잡도는 O(N)입니다.
기타 변수: int형 변수 min, max, N과 Scanner 객체가 사용됩니다. 이들은 모두 상수 공간을 사용하므로 O(1)입니다.

O(N)+O(1)=O(N) 공간 복잡도는 O(n)  

 

 

 

 

3. 정상 코드

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {

        // 입력을 위한 객체 생성
        Scanner scan = new Scanner(System.in);

        // 정수의 개수 N 입력
        int N = scan.nextInt();
        // 정수의 개수 유효성 검사
        if (N < 1 || N > 1000000) {
            System.out.println("정수의 개수 N은 1 ≤ N ≤ 1,000,000이어야 합니다.");
            return;
        }

        // 정수를 저장할 배열 생성
        int[] nums = new int[N];
        // 정수의 범위 유효성 검사와 배열에 입력
        for (int i = 0; i < N; i++) {
            nums[i] = scan.nextInt();
            if (nums[i] < -1000000 || nums[i] > 1000000) {
                System.out.println("정수의 범위는 -1,000,000 ≤ 정수 ≤ 1,000,000이어야 합니다.");
                return;
            }
        }


        // 최솟값 최대값을 최조의 정수로 초기화
        int min = nums[0];
        int max = nums[0];
        for (int i = 1; i < N; i++) {
            if (nums[i] < min) {
                min = nums[i];
            }
            if (nums[i] > max) {
                max = nums[i];
            }
        }

        // 최솟값과 최댓값 출력
        System.out.println(min + " " + max);

        // Scanner 객체 닫기
        scan.close();
    }
}

 

 

 

 

 

추가 정리

 

 

유효성 검사 코드에서 return;   return 0; 

최솟값, 최댓값 변수 선언 후 초기화는 임의로 0으로 하면 안 된다.

입력받은 정수가 모두 양의 정수이면 최솟값은 임의로 정한 0으로 잘못된 결괏값을 출력하게 된다