[알고리즘] 백준 10818번 - 최소, 최대 문제 풀이 (Java)

백준 10818번 문제 "최소, 최대"를 풀면서 알게 된 내용을 공유하려 한다.

두 가지 방법을 사용할건데 하나는 정렬, 다른 하나는 단일 순회 방식을 사용할 것이다.

이 문제는 N개의 정수가 주어졌을 때 최솟값과 최댓값을 구하는 간단한 문제다.

---

처음 작성한 코드 (정렬 사용)

처음에는 배열을 정렬한 후 첫 번째 요소와 마지막 요소를 출력하는 방식으로 접근했다.

import java.util.*;
import java.io.*;
public class Main {
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());
    int N = Integer.parseInt(st.nextToken());
    int[] arr = new int[N];
    st = new StringTokenizer(br.readLine());
    for (int i = 0; i < N; i++) {
      arr[i] = Integer.parseInt(st.nextToken());
    }
    Arrays.sort(arr);
    System.out.printf("%d %d\n", arr[0], arr[N - 1]);
  }
}

이 코드는 다음과 같은 과정으로 작동한다.

1. BufferedReader를 이용해 입력을 받는다.
2. 첫 번째 줄에서 정수의 개수 N을 읽는다.
3. 크기가 N인 배열을 생성한다.
4. 두 번째 줄의 N개 정수를 배열에 저장한다.
5. 배열을 정렬한다.
6. 정렬된 배열의 첫 번째 요소(최솟값)와 마지막 요소(최댓값)를 출력한다.

이 코드로 문제를 풀었을 때 정답은 맞았지만, 실행 시간이 1260ms로 꽤 오래 걸렸다.

뭔가 이상함을 느꼈다.

---

시간 복잡도와 성능 이슈

왜 이렇게 오래 걸렸을까? 정렬을 사용한 방식의 시간 복잡도를 분석해 보았다.

 

• 입력 받기: O(N)
• 배열 정렬: O(N log N)
• 최솟값과 최댓값 출력: O(1)

전체 시간 복잡도는 O(N log N)으로, 정렬 과정이 가장 많은 시간을 차지한다.

문제의 제약 조건을 보면 N이 최대 1,000,000까지 가능하므로, 정렬은 약 1,000,000 * log(1,000,000) ≈ 20,000,000번의 연산을 필요로 할 수 있다. 이는 상당히 큰 수치라고 본다.

게다가 정렬은 추가 메모리를 사용하기도 한다.

Java의 Arrays.sort()는 기본적으로 TimSort 알고리즘을 사용하는데,
이는 병합 정렬과 삽입 정렬을 합친 하이브리드 정렬 알고리즘이다.

(이 과정에서 추가적인 메모리 공간이 필요하다.)

---

최적화된 코드 (단일 순회)

더 효율적인 방법을 찾아보았다.

배열 전체를 한 번만 순회하면서 최솟값과 최댓값을 동시에 찾는 접근 방식이다.

import java.util.*;
import java.io.*;
public class Main {
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int N = Integer.parseInt(br.readLine());
    StringTokenizer st = new StringTokenizer(br.readLine());
    
    int min = Integer.MAX_VALUE;
    int max = Integer.MIN_VALUE;
    
    for (int i = 0; i < N; i++) {
      int num = Integer.parseInt(st.nextToken());
      min = Math.min(min, num);
      max = Math.max(max, num);
    }
    
    System.out.printf("%d %d\n", min, max);
  }
}

 

이 코드의 작동 방식은 다음과 같다.

1. 최솟값 변수 min을 가능한 가장 큰 정수값(Integer.MAX_VALUE)으로 초기화한다.
2. 최댓값 변수 max를 가능한 가장 작은 정수값(Integer.MIN_VALUE)으로 초기화한다.
3. 배열에 저장하지 않고 입력을 한 번만 읽으면서 각 숫자마다:
   • 현재 숫자가 min보다 작으면 min을 갱신한다.
   • 현재 숫자가 max보다 크면 max를 갱신한다.
4. 최종적으로 계산된 min과 max를 출력한다.

---

두 접근 방식 비교 분석

시간 복잡도 비교

• 정렬 방식: O(N log N)
• 단일 순회 방식: O(N)

N이 큰 경우(이 문제에서는 최대 1,000,000) 차이가 확연히 드러난다. 예를 들어 N이 1,000,000일 때,

• 정렬 방식은 약 20,000,000번의 비교 연산
• 단일 순회 방식은 정확히 1,000,000번의 비교 연산

공간 복잡도 비교

• 정렬 방식: O(N) - 전체 배열을 저장해야 함
• 단일 순회 방식: O(1) - 상수 개의 변수만 사용

위가 단일 순회 방식, 밑이 정렬 방식(약 3배 차이)

---

회고 및 배운 점

이 문제를 통해 알고리즘 문제를 풀 때 단순히 정답을 찾는 것뿐만 아니라 효율적인 해결책을 찾는 것의 중요성을 깨달았다.

처음에는 배열을 정렬하면 쉽게 최솟값과 최댓값을 찾을 수 있다고 생각했지만, 그것이 최선의 방법이 아니었다.

자료구조와 알고리즘 공부도 더 깊이 해야겠다는 생각이 들었다.

특히 시간 복잡도와 공간 복잡도를 항상 염두에 두고 문제를 접근하는 습관을 들여야겠다.

또한 Java의 라이브러리 함수들(Arrays.sort(), Math.min(), Math.max() 등)의 내부 동작 원리에 대해서도 더 공부해볼 필요가 있다고 느꼈다.

어떤 상황에서 어떤 함수를 사용하는 것이 효율적인지 더 깊이 이해하면 더 좋은 코드를 작성할 수 있을 것이라고 생각한다!!!