4. 자바 배열과 반복문 (4) 연습 - 배열의 최댓값 구하기

이번 포스트에서는 반복문 연습의 일환으로 배열에서 최댓값을 구하는 코드를 짜 보도록 하겠다.

예상 독자

• 자바를 배우고 싶은 누구나
• JDK와 IDE를 설치한 자바 학습자. ( 1. 자바 설치 및 개발환경 설정 )
• char를 공부한 자바 학습자. ( 2. 자바 변수와 자료형  (1) char )
• boolean을 공부한 자바 학습자. ( 2. 자바 변수와 자료형 (2) boolean )
• byte, short, int, long을 공부한 자바 학습자. ( 2. 자바 변수와 자료형 (3) byte, short, int, long )
• float과 double을 공부한 자바 학습자. ( 2. 자바 변수와 자료형 (4) float, double )
• if-else문의 사용 방법을 알고있는 자바 학습자. ( 3. 자바 조건문 (1) if-else )
• 자바 배열을 공부한 자바 학습자. ( 4. 자바 배열과 반복문 (1) 배열 )

배열의 최댓값 구하기

다음과 같이 임의로 선언된 배열이 있다. 이 배열은 항상 1개 이상의 값을 가지고 있다고 가정한다. 반복문을 이용해 이 배열에서 가장 큰 값을 찾는 코드를 짜 보자.

public class Main {
    public static void main(String[] args) {
        int[] numbers = {3, 2, 14, 21, 100, 4, 2, 1};
    }
}

이 배열에서 가장 큰 값이 무엇인가? 100이다. 지금부터 어떤 배열에서 가장 큰 수를 찾는 코드를 짜 보도록 하겠다. 여러분도 잠시 멈추고 어떻게 해야 배열에서 가장 큰 수를 구할 수 있는지 생각해보라. 우리의 뇌는 어떻게 100이 가장 큰 수라는 것을 알았는가? 바로 다른 모든 수들과 비교했을 때 100이 가장 크기 때문에 그랬을 것이다. 이런 일련의 과정은 우리의 뇌 속에서 너무 빠르게 일어나서 우리는 실제로 뇌가 어떤 과정을 거쳐 100이 가장 크다는 결론을 도출했는지 알지 못할 때가 많다. 이럴 때 본인이 어떻게 이 값을 도출했는지 깊게 생각 해 보는 것이 프로그래밍 로직을 짜는데 도움이 될 수 있다. 로직이 어떻게 되는가? 일단 3에서부터 시작해서 2가 3보다 큰가? 아니다 그러니 다음으로 아직까지는 3이 가장 큰 수이다. 그 다음으로 넘어가니 14가 있다. 14는 3보다 크므로 새로운 최댓값은 14이다 그리고 다음 엘리먼트로 넘어가면 21이 있다. 마찬가지로 21이 14보다 크니 새 최댓값은 21이다. 같은 방법으로 100이 최댓값이 된다. 100 다음에는 4가 나온다. 4는 100보다 크지 않다 그러므로 여전히 최댓값은 100이다. 나머지 두 엘리먼트도 같은 방법으로 비교된다.

public class Main {
    public static void main(String[] args) {
        int[] numbers = {3, 2, 14, 21, 100, 4, 2, 1};
        int max;
        for(int i = 0; i < numbers.length; i++) {
            // 스스로 짜보기
        }
        System.out.println(max);
    }
}

방금 구성한 로직을 말로 해보면 다음과 같다. 우리는 최댓값을 항상 기억 할 것이다. 최댓값의 초기값은 numbers[0]이고 그 다음부터 하나씩 배열의 엘리먼트를 비교하며 현재 최댓값보다 엘리먼트의 값이 더 크면 이 엘리먼트의 값을 새 최댓값으로 지정한다.

이를 코드로 짜기 위해서는 최댓값을 저장할 변수와, 배열을 반복 할 반복문이 필요하다. 우리는 max라는 변수에 가장 큰 값을 저장 할 것이다. 내부를 스스로 짜 보고 아래로 넘어가도록 하자.

public class Main {
    public static void main(String[] args) {
        int[] numbers = {3, 2, 14, 21, 100, 4, 2, 1};
        int max = numbers[0];
        for(int i = 0; i < numbers.length; i++) {
            if(max < numbers[i]) {
                max = numbers[i];
            }
        }
        System.out.println(max);
    }
}
실행 결과:
100

우리는 반복문 내부에 max와 i번째 배열의 값을 비교하는 부분을 넣어 max보다 i번째 배열의 값이 더 큰 경우 max의 값을 교체 해 주는 로직을 만들 수 있다. (위와 똑같은 코드를 짠 게 아니라도 괜찮다. 결과만 정확히 나오면 된다.)

배열에 다른 값들을 넣어 테스팅 해 보자. 적어도 3개 이상 테스트 해 보도록 한다. 

끝

이번 포스트에서는 반복문을 이용해 배열의 최댓값을 구하는 알고리즘을 짜 보았다. 이 예제 말고 다른 예제도 해보도록 하자.

1. 위 코드를 수정해 최솟값을 찾는 로직으로 바꿔보라.

2. 정렬되어있는 배열과 목푯값이 있다. 이 목푯값이 있는 위치의 인덱스를 출력하라.

public class Main {
    public static void main(String[] args) {
        int[] numbers = {1, 1, 2, 3, 14, 21, 33, 100};
        int goal = 21;
        // 답 = 5
    }
}

3. 위의 코드를 작성했다면 문제를 조금 변형 해 보자. 만약 목푯값이 배열에 없다면 목푯값이 있어야 할 인덱스가 어딘지 구해 출력해라.

public class Main {
    public static void main(String[] args) {
        int[] numbers = {1, 1, 2, 3, 14, 21, 33, 100};
        int goal = 10;
        // 답 = 4 - numbers[3] 다음에 나와야 하므로 4
    }
}

2번과 3번의 경우 리트코드-Search Insert Position에서 가져왔으며 해설은 [코딩연습] Search Insert Position 숫자를 넣을 자리 찾기에서 확인 할 수 있다.

참고 (시간복잡도 계산법)

이 알고리즘의 시간복잡도(Time Complexity)는 O(n)이고 공간 복잡도(Space Complexity)는 O(1)이다. 이유는 시간 복잡도의 경우 numbers의 크기에 따라 반복문을 전부 도는 시간이 길어지기 때문이다. 예를들어 반복문을 한바퀴 도는데 1초가 걸린다고 가정 했을 때, numbers의 길이가 100이라면 100초, 1000이라면 1000초, 10000이라면 10000초가 걸린다. n일때는 n초가 걸리므로 O(n)이다. 반면 시간 복잡도는 반복문의 길이에 상관없이 우리는 항상 max라는 값 하나만 선언하므로 O(1)이다. 

다음 포스트:4. 자바 배열과 반복문 (5) while