[알고리즘/백준] 10818번 :: 최소, 최대 (C++)

mingguriguri·2022년 5월 17일
0
post-thumbnail

문제 ✍🏻 :: [10818번] 최소, 최대

(초록색 글자 클릭 시 문제로 이동)


풀이 🔍

내가 처음 한 풀이

#include <iostream>

using namespace std;

int main()
{
    // N을 입력받는다
    int N;
    cin >> N;
    
	//최솟값과 최댓갑의 초기값 설정
    int max = -1000000;
    int min = 1000000;

    //배열을 정의
    int arr[N+1]; 

    for (int i = 0; i < N; i++) {
        cin >> arr[i];
		 //배열 값이 max값보다 크다면 그 값을 max에 저장
        if (arr[i] > max) {
            max = arr[i];
        }
         //배열 값이 min값보다 작다면 그 값을 min에 저장
        if (arr[i] < min) {
            min = arr[i];
        }       
    }
    cout << min << " " << max;

    return 0;
}
  1. 처음에 초깃값 설정에서 애를 먹었다. 초깃값 설정을 제대로 하지 못해 계속 에러가 났기 때문

  2. 답은 문제 속에 있다. 문제에서 '모든 정수는 -1,000,000보다 크거나 같고, 1,000,000보다 작거나 같은 정수이다.'라고 하였다.
    즉, 최소 -1,000,000 부터 최대 1,000,000이라고 하였다.
    min 값은 1,000,000으로 초기화, max 값은 -1,000,000초기화 하였다.

  3. 두 값을 비교하며 max보다 크면 max에 집어넣고, 차례대로 비교하는 식으로 코드를 구성하였다.

결과

참고한 풀이 (Stranger's LAB)

<1>
이 글쓴이는 첫번째 방법으로 sort()함수를 사용한다.

// sort(배열의 시작 주소, 배열의 마지막 주소)
sort(array + 0, array + N);
//시작주소(포함) ~ 끝 주소(미포함) 범위를 '오름차순'으로 정렬

이 함수를 사용하면 풀이는 다음과 같다.

#include <iostream>
#include <algorithm>
 
using namespace std;
 
int main(int argc, const char * argv[]) {
 
	ios_base::sync_with_stdio(0);
 
	int N;
	cin >> N;
 
	int array[N+1];
 
	for(int i = 0; i < N; i++) {
		cin >> array[i];
	}
 
	sort(array, array + N);		// 0 ~ N-1 범위 정렬
 
	cout << array[0] << " " << array[N - 1];
 
	return 0;
 
}

<2>
2번째 방법으로는 나와 비슷한 방법을 사용하셨다. 그런데 다른 점은 초기값이었다.
나는 초기값을 다르게 해도, 백준에서는 맞게 나오긴 했다. 하지만 더 정확할수록 좋으니, 해당 풀이를 참고하였다.

#include <iostream>
 
using namespace std;
 
int main(int argc, const char * argv[]) {
 
	ios_base::sync_with_stdio(0);
 
	// minValue, maxValue의 초기값
	int minValue = 1000001;
	int maxValue = -1000001;
 
	int N;
	cin >> N;
 
	int inputValue;
	for(int i = 0; i < N; i++) {
		cin >> inputValue;
 
		// 입력으로 들어온 값이 minValue보다 작다면 min을 inputValue로 갱신
		if (inputValue < minValue) {
			minValue = inputValue;
		}
		// 입력으로 들어온 값이 maxValue보다 크다면 max를 inputValue로 갱신
		if (inputValue > maxValue) {
			maxValue = inputValue;
		}
	}
 
	cout << minValue << " " << maxValue;
	return 0;

몰랐는데, 이 분이 하신 것처럼 이 문제는 꼭 배열을 사용할 필요는 없다. 저장할 필요 없이 입력 들어온 값과 max/min 값을 비교해주기만 하면 되기 때문! 즉, 입력된 모든 값을 정렬하는 것이 아닌 최대 최소만 출력하는 것이기 때문이다.

나의 경우 배열을 이용하였고 이 분의 풀이에서 내가 부족했던 부분을 참고하였다. 배열을 이용하였기에 메모리를 많이 차지하였던 것 같다.

최종 보충한 풀이

1. 성능 보완
2. 코드들의 위치 변경
3. 배열대신 변수로 수정

이 3가지를 바탕으로 코드를 최종 수정하였다.

#include <iostream>

using namespace std;

// 1차원배열

int main()
{
    ios_base::sync_with_stdio(0);

    //최솟값과 최댓갑의 초기값 설정
    int max = -1000001;
    int min = 1000001;
    
    //입력값 : input
    int input;

    // N 입력
    int N;
    cin >> N;

    for (int i = 0; i < N; i++) {
        cin >> input;

        //입력값이 max값보다 크다면 그 값을 max에 저장
        if (input > max) {
            max = input;
        }
        
        //입력값이 min값보다 작다면 그 값을 min에 저장
        if (input < min) {
            min = input;
        }       
    }
    cout << min << " " << max;
    return 0;
}

1번째에 했던 것보다 시간은 75% 단축됐고, 용량은 50% 단축되었다.


느낀 점 🤔

  • 앞서 얘기했던 것처럼, 초기화를 어떤 값으로 해야할지 어려웠음
    => 그러나! 답은 문제 속에 있다!
    => 문제에 있는 조건들 최대한 활용할 것
  • 꼭 배열을 쓸 필요가 없다면 과감하게 더 효율적인 방식을 택할 것
    => 문제를 풀면서 배열을 쓸 필요가 없다는 생각을 아예 하지 못했음. 다른 블로그 보고 배웠음

Reference

profile
To be "irreplaceable"

0개의 댓글