최소, 최대 값 찾는 가장 빠른 알고리즘 C++ / Java / 파이썬

백준 10818번을 풀면서 최소, 최대값 찾는 가장 빠른 알고리즘을 공부해 봅시다.

 

최소, 최대 값을 찾는 문제입니다.

주어진 숫자들에서 최소, 최대를 찾으려면 결국 모든 숫자를 1번씩은 봐야합니다. 

O(N) 시간복잡도로 반복문 1회가 필요한 간단한 문제입니다.

이보다 좋은 해결법은 없습니다.

 

https://www.acmicpc.net/problem/10818

10818번: 최소, 최대

 

정수의 개수 N은 100만개로 1억이 넘어가지 않는 숫자라서 1초 이내에 수행이 완료됩니다.

시간초과가 나지 않습니다.

 

입력범위는 -1,000,000 ~ 1,000,000 으로 합이나 곱과 같은 수학계산이 필요하지 않으므로 일반적인 int 데이터형을 사용하면 됩니다. 

 

시간초과나 데이터형 선택에도 특별히 고려할 내용은 없네요.

빠르게 풀어봅시다.

 

1. C++

max와 min 변수에 넣는 숫자를 보세요.

max는 최대값을 저장하는 변수로 가장 작은 입력값보다 더 작은 초기값을 세팅합니다.

min은 최소값을 저장하는 변수로 가장 큰 입력값보다 더 큰 초기값을 세팅합니다.

987654321 숫자를 자주 이용합니다.

이 숫자는 int형을 벗어나지 않으면서 실수없이 입력가능한 매우 적절한 숫자입니다.

코딩 대회를 준비하시는 분께는 아주 좋은 팁이 될 것 입니다.

#include <stdio.h>

int main() {
	int N, temp;
	int max = -987654321;
	int min = 987654321;

	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		scanf("%d", &temp);
		if (max < temp) {
			max = temp;
		}
		if (min > temp) {
			min = temp;
		}
	}
	printf("%d %d", min, max);
	return 0;
}

 

 

2. JAVA

C++과 동일한 소스입니다.

C와 JAVA의 풀이는 너무 비슷해서 특별히 배울점이 없다면 번갈아가며 풀이해야 겠네요.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

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 max = -987654321;
		int min = 987654321;

		for (int i = 0; i < N; i++) {
			int temp = Integer.parseInt(st.nextToken());

			if (max < temp) {
				max = temp;
			}
			if (min > temp) {
				min = temp;
			}
		}
		System.out.println(min + " " + max);
    }
}

 

 

3. Python 파이썬

파이썬은 특별하게 소팅(정렬)을 사용했습니다.

리스트로 입력을 받고 오른차순으로 소팅합니다.

그러면 0번째는 가장 작은수, N-1번째는 가장 큰수가 들어갈 것입니다.

소팅을 하면 시간복잡도가 O(NlogN)지만 숫자 개수가 100만개 정도로 대세에 영향이 없습니다.

N = int(input())

arr = list(map(int, input().split()))
arr.sort()

print(arr[0], arr[N-1])

 

최소 최대는 알고리즘에 있어 기본 중에 기본입니다.

뭐든 기초가 튼튼해야죠.