백준(BAEKJOON): 최소, 최대(10818번)

문제

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

입력

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

출력

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

예제 입력 1

5
20 10 35 30 7

예제 출력 1

7 35

출처 문제를 만든 사람: baekjoon

해설

좀 짜증 나는 문제다. 이 문제는 BOJ의 단계별로 풀어보기에서 1차원 배열로 분류되어 있다. 그래서 문제 풀이를 위해서는 반드시 1차원 배열을 써야 하리라 짐작했다. 최대 1,000,000개의 값이 주어질 수 있으므로 1,000,000개의 int형 변수를 갖는 배열을 선언하는 방법이 있을 것이다. 그러나 이 단순한 프로그램을 위해 이만큼의 메모리를 사용하는 것은 비효율적이므로 malloc을 사용하여 메모리를 동적 할당하는 방법으로 선회하였다. 배열이 만들어졌으니 단순한 정렬 코드로 추가하여 아래와 같이 프로그램을 완성하였다. 높은 수부터 낮은 수로 정렬되므로 결과는 numPtr[i - 1]과 numPtr[0] 순으로 출력하도록 하있다.

아래 코드는 malloc을 사용하기 위해 해더로 stdlib.h을 추가하였다. 동적으로 할당한 메모리는 사용한 후에는 반드시 free로 풀어주는 것을 잊지 말자!

소스코드 c: 동적 할당

#include <stdio.h>
#include <stdlib.h>

int main(int argc, char *argv[])
{
    int num, i, j;
    char buffer;

    scanf("%d", &num);

    int *numPtr = malloc(sizeof(int) * num);

    for (i = 0; i < num; i++) {
        scanf("%d", (numPtr + i));
    }

    for (i = 0; i < num; ++i) {
        for (j = i + 1; j < num; ++j) {
            if (numPtr[i] < numPtr[j]) {
                buffer = numPtr[i];
                numPtr[i] = numPtr[j];
                numPtr[j] = buffer;
            }
        }
    }

    printf("%d %d\n", numPtr[i - 1], numPtr[0]);
    free(numPtr);
    return 0;
}

그러나 채점 결과는 부끄럽게도 시간 초과였다. 이게 뭐냐. 분명 배열을 써서 풀라는 문제가 아니었나? 출제자의 의도을 파악하고 코딩을 했다고 내심 자신만만했었는데 이런 결과라니 부끄럽다 못해 짜증이 났다. 결국 아래와 같이 코드에서 배열을 걷어낸 후에야 맞았습니다!!를 만날 수 있었다.

소스코드 c: 배열을 쓰지 않고

#include <stdio.h>

int main(int argc, char *argv[])
{
    int min = 1000000, max = -1000000;
    int count, temp, i;

    scanf("%d", &count);

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

    printf("%d %d\n", min, max);

    return 0;
}

오늘의 교훈: 개 잡는 데 소 잡는 칼 꺼내지 말자.

소스 코드 python

count = int(input())
max = -1000000
min = 1000000
input_num = map(int, input().split())

for item in input_num:
    if item > max:
        max = item

    if item < min:
        min = item

print(min, max)

입력 형식을 맞추기 위해 1번 라인이 있을 뿐 전체 코드에서는 사용되지 않았다. 파이썬에서는 실제 비교할 수를 리스트로 받아 저장하므로 for문의 반복 횟수를 정하는 데도 소용되지 않는 것이다. 리스트인 input_num이 이터레이터형이므로 그 안의 멤버들을 순서대로 꺼내서 비교하면 끝!