[알고리즘] 최솟값, 최댓값 구하기

01. 나열된 수에서 최솟값과 최댓값 구하기

---

1) 문제 정의

여러 개의 수가 배열에 있을 때 그중 가장 큰 값과 작은 값을 찾고 해당 위치 구하기
단, 반복문은 한번만 사용

2) 수의 예

[10, 55, 23, 2, 79, 101, 16, 182, 30, 45]

---

3) 해결

public class MinMaxProblem {

    public static void main(String[] args) {

        int[] numbers = {10, 55, 23, 2, 79, 101, 16, 182, 30, 45};

        int min = numbers[0]; // 초기값 설정 : 배열 numbers 안에서 0번째
        int max = numbers[0]; // 초기값 설정 : 배열 numbers 안에서 0번째

        int minPos = 0; // 최솟값 위치 변수
        int maxPos = 0; // 최댓값 위치 변수

        for(int i = 1; i<numbers.length; i++) {

            if(min > numbers[i]) {
                min = numbers[i];
                minPos=i+1;
            }

            if(max < numbers[i]) {
                max = numbers[i];
                maxPos=i+1;
            }
        }

        System.out.println("최솟값은 " + minPos + "번째의 " + min + "입니다.");
        System.out.println("최댓값은 " + maxPos + "번재의 " + max + "입니다.");

    }
}

4) 풀이

조건에서 주어진 수들을 넣은 numbers라는 이름의 배열을 생성한다.

최솟값은 min, 최댓값은 max라고 변수를 설정하고, 변수의 0번째를 지정해주면서 초기화를 해준다.

위치도 구해야하기 때문에 minPos, maxPos 변수를 생성하고, 마찬가지로 초기화를 해준다.

배열의 사이즈만큼 반복할 for문을 사용한다.

for 안에는 연결되어있지 않은 if문 두 개를 사용한다.

하나는 최솟값을 구하는 if문, 나머지 하나는 최댓값을 구하는 if문이다.

처음 설정한 min과 max의 초기값은 numbers 배열의 0번째 숫자. 즉, 10에 해당한다.

for문의 초기값(i)는 1이므로 numbers[i]는 numbers[1]로 55에 해당한다. 

if문의 조건대로 비교를 해보면 10은 55보다 작으니 min값은 변함이 없고, max 값은 numbers[1]인 55로 대입한다.

그리고 이어서 maxPos 변수는 2가 되어 위치가 2를 나타낸다.

여기서 조심해야할 포인트
우리는 숫자를 셀 때 1부터 시작하지만, 배열과 같이 컴퓨터 내에서는 보통 0부터 시작한다.
배열의 0번째가 위치 1에 해당한다.

또 하나의 포인트
min의 if문과 max의 if문은 별개로 작동한다.
만약 min의 if문의 조건이 true가 아니라면 내부로 들어가지 않고 다음 if문으로 넘어가게 된다.

위 같은 방식으로 배열의 길이만큼 반복을 하고,

최종적으로 출력된 min, max, minPos, maxPos 값이 우리가 원하는 결과값이다.

---

5) 결과

최솟값, 최댓값 구하기 결과 화면

조건에서 주어진 수 [10, 55, 23, 2, 79, 101, 16, 182, 30, 45]에서

최솟값은 2이며 위치는 4번째, 최댓값은 182이며 위치는  8번째라는 것을 알 수 있다.

5) 수행 시간 분석

- 반복문을 한번만 수행해서 원하는 값을 모두 찾을 수 있다.

- 이 경우 수행 속도는 나열된 수의 개수에 비례한다.

- 시간복잡도는 O(n)이 된다.

시간 복잡도 : 작성한 코드의 실행시간 (입력값과 연산 수행 시간의 상관관계를 나타내는 척도) 
* n = 자료의 수이며 Big-O 표기법에 따라 나타낸다.