[백준알고리즘/1차원 배열] 10818번 문제 : 최소, 최대(자바/JAVA)

안녕하세요

백준알고리즘 단계별로 풀어보기 4단계 10818번 문제 최소, 최대를 풀어봤습니다

1차원 배열의 첫 번째 문제라서 그렇게 어렵지 않았습니다

오히려 문제를 보는데 배열 없이도 충분히 풀 수 있는 문제였습니다

제가 풀었던 여러 가지 방식에 대해서 설명해보겠습니다!

 

문제

N개의 정수가 주어진다. 이때, 최솟값과 최댓값을 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 정수의 개수 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 N개의 정수를 공백으로 구분해서 주어진다. 모든 정수는 -1,000,000보다 크거나 같고, 1,000,000보다 작거나 같은 정수이다.

 

출력

첫째 줄에 주어진 정수 N개의 최솟값과 최댓값을 공백으로 구분해 출력한다.

 

---

문제풀이

총 문제는 다섯가지 방식으로 풀었습니다

1. 맨 처음 정답을 해결했을 때 제가 사용한 방식입니다

 For구문, 배열을 사용해서 구현한 방식입니다

2. For구문과 배열을 사용하지 않고 구현한 방식입니다

3. Arrays.sort를 사용해서 구현한 방식입니다

4. while문을 사용, hasMoreTokens를 사용해 구현했습니다

5. 문제에서 초기값 범위를 이용해서 초기값을 세팅해서 while문을 사용해 구현했습니다

 

1. 반복문을 두 번 사용해서 문제를 풀었습니다

 첫 번째 반복문에서는 배열에 데이터를 넣고, 두 번째 반복문에서는 MIN, MAX 값을 구합니다

 생각지도 못했지만 다섯가지방식 중에서 속도가 제일 빠르게 나왔습니다;;

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 선언
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		// 반복할 갯수 선언
		int n = Integer.parseInt(br.readLine());

		// StringTokenizer로 입력
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		
		// 배열 변수 선언
		int[] array = new int[n];
				
		// N만큼 반복
		for(int i = 0; i < n; i++)
		{
			// 배열의 데이터 입력
			array[i] = Integer.parseInt(st.nextToken());			 
		}

		// min, max 변수 선언 및 초기값 설정
		int min = array[0];
		int max = array[0];
		
		// N만큼 반복
		for(int i = 1; i < n; i++)
		{
			// MIN, MAX를 비교해서 구한다
			if(min > array[i])
			{
				min = array[i];
			}
			
			if(max < array[i])
			{
				max = array[i];
			}
		}
		
		// 결과 출력
		System.out.print(min + " " + max);
	}
}

 

2. 배열을 사용하지 않고 반복문에서 바로바로 MIN과 MAX을 구해서 결과를 출력해줍니다

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 선언
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		// 반복할 갯수 선언
		int n = Integer.parseInt(br.readLine());

		// StringTokenizer로 입력
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");

		// 첫 번째 값 입력
		int b = Integer.parseInt(st.nextToken());	

		// min, max 변수 선언 및 초기값 설정
		int min = b;
		int max = b;
				
		// N만큼 반복
		for(int i = 0; i < n - 1; i++)
		{
			// 데이터 입력
			int a = Integer.parseInt(st.nextToken());	

			// MIN, MAX를 비교해서 구한다
			if(min > a)
				min = a;

			if(max < a)
				max = a;
		}

		// 결과 출력
		System.out.print(min + " " + max);
	}
}

 

3. Arrays.sort를 사용해서 구현한 방식입니다

 java 기본 메소드를 사용해서 구현해서 그런지 속도는 역시 제일 느립니다

 아마 구현하는 방식 중에서는 이 방법이 제일 간단할 것 같습니다

 이 방식은 제 머리에서 나온 것은 아니고 여기 블로그를 참고해서 구현했습니다

st-lab.tistory.com/43

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

public class Main3 {
	public static void main(String[] args) throws IOException {	
		// BufferedReader 선언
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		// 반복할 갯수 선언
		int n = Integer.parseInt(br.readLine());

		// StringTokenizer로 입력
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");

		// 배열 변수 선언
		int[] array = new int[n];

		// N만큼 반복
		for(int i = 0; i < n; i++)
		{
			// 데이터 입력
			array[i] = Integer.parseInt(st.nextToken());			 
		}

		// 배열.sort 사용
		Arrays.sort(array);

		// 결과 출력
		System.out.print(array[0] + " " + array[n - 1]);
	}
}

 

4. for문을 사용하지 않고 while문과 hasMoreTokens과 배열을 사용하지 않고 구현했습니다

 배열을 사용하지 않기 때문에 맨 처음에 입력받은 값을 사용할 일이 없으므로 정답을 위해 입력을 해주고있습니다

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 선언
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		// 사용하지 않지만 값 입력
		Integer.parseInt(br.readLine());

		// StringTokenizer로 입력
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");

		// 초기값 세팅
		int b = Integer.parseInt(st.nextToken());	

		// min, max 변수 선언 및 초기값 설정
		int min = b;
		int max = b;
				
		// 반복문 실행
		while(st.hasMoreTokens())
		{
			// 데이터 입력
			int a = Integer.parseInt(st.nextToken());

			// MIN, MAX를 비교해서 구한다
			if(min > a)
				min = a;

			if(max < a)
				max = a;
		}

		// 결과 출력
		System.out.print(min + " " + max);
	}
}

 

5. 마지막 방법입니다

이 로직을 구현할 때 제일 난감했던 부분이 MIN과 MAX의 초기값 이었습니다

배열을 이용해서 구현하면 상관없지만 배열을 이용하지 않을 경우 MIN, MAX의 초기값을 지정해줘야했습니다

여기서 문제 조건에 들어가는 값은 모든 정수는 -1,000,000보다 크거나 같고, 1,000,000보다 작거나 같은 정수이다

정수의 값을 고정시켜줍니다

MIN은 1000001로 선언, MAX는 -1000001로 초기값을 세팅하면 간단하게 구현을 할 수 있습니다

public class Main5 {
	public static void main(String[] args) throws IOException {
		// BufferedReader 선언	
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		// 사용하지 않지만 값 입력
		Integer.parseInt(br.readLine());

		// StringTokenizer로 입력
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");

		// min, max 변수 선언 및 초기값 설정
		int min = 1000001;
		int max = -1000001;

		// 반복문 실행
		while(st.hasMoreTokens())
		{
			// 데이터 입력
			int a = Integer.parseInt(st.nextToken());

			// MIN, MAX를 비교해서 구한다
			if(min > a)
				min = a;

			if(max < a)
				max = a;
		}

		// 결과 출력
		System.out.print(min + " " + max);
	}
}

 

여기까지 다섯 가지 방식을 이용해서 알고리즘을 구한 방식입니다

마지막으로 다섯 가지 방식의 속도 비교입니다

---

속도 비교

 

여기까지 백준알고리즘 10818번 문제를 풀은 내용이었습니다

이 글이 알고리즘 공부를 하는 분들께 도움이 되었으면 좋겠습니다!

 

다음 문제 : 2021.05.03 - [알고리즘/알고리즘JAVA] - [백준알고리즘/1차원 배열] 2477번 문제 : 숫자의 개수(자바/JAVA)