C++ 코딩테스트 강좌, 최솟값 찾기 2

코딩테스트에서 가장 흔하게 등장하는 문제 중 하나는 배열에서 주어진 조건에 맞는 최솟값 또는 최댓값을 찾는 문제입니다. 이번 강좌에서는 ‘최솟값 찾기 2’라는 주제로, 실제 코딩테스트에서 자주 출제되는 문제를 소개하고, 이를 C++로 해결하는 방법을 자세히 설명하겠습니다.

문제 설명

주어진 배열에서 특정 조건을 만족하는 최솟값을 찾아 출력하는 문제입니다.

문제 정의

정수 N이 주어지고, N개의 정수가 포함된 배열 A가 주어집니다. 이때, 배열의 모든 요소 중에서 두 번째로 작은 값을 출력하는 프로그램을 작성하세요.

입력 형식

첫 번째 줄에 정수 N (2 ≤ N ≤ 100,000) 이 주어집니다. 두 번째 줄에는 N개의 정수가 공백으로 구분되어 주어집니다. 각 정수는 -1,000,000,000 이상 1,000,000,000 이하입니다.

출력 형식

두 번째로 작은 정수를 출력합니다. 두 번째로 작은 정수가 없다면 “No Second Minimum”를 출력합니다.

예제 입력 및 출력

문제 해결 접근법

이 문제를 해결하기 위해서는 배열의 요소를 정렬하는 방법과 중복 처리를 잘 이해해야 합니다. 우리가 찾고자 하는 값은 두 번째로 작은 값이므로, 간단히 배열을 정렬한 후 고유한 값들로부터 두 번째 값을 뽑아내면 됩니다.

알고리즘 단계

1. 배열을 입력받은 후 정렬한다.
2. 정렬된 배열에서 중복을 제거하여 고유한 값의 리스트를 만든다.
3. 고유한 값의 리스트에서 두 번째 최소값이 존재하는지 확인하고 출력한다.

C++ 구현

이제 위의 알고리즘을 C++로 구현해보겠습니다. 아래는 C++ 코드입니다:

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>

using namespace std;

int main() {
    int N;
    cin >> N;

    vector<int> A(N);
    
    for (int i = 0; i < N; i++) {
        cin >> A[i];
    }

    // 배열을 정렬
    sort(A.begin(), A.end());

    // 고유한 값을 저장할 집합
    set<int> uniqueValues(A.begin(), A.end());

    // 두 번째로 작은 값 찾기
    if (uniqueValues.size() < 2) {
        cout << "No Second Minimum" << endl;
    } else {
        auto it = uniqueValues.begin();
        it++;
        cout << *it << endl;
    }

    return 0;
}
    

코드 설명

• #include <iostream>: 입출력을 위한 라이브러리입니다.
• #include <vector>: 동적 배열을 사용할 수 있게 합니다.
• #include <algorithm>: 정렬 함수와 기타 알고리즘 관련 함수들을 사용하게 합니다.
• #include <set>: 집합(중복을 허용하지 않는 데이터 구조)을 사용하기 위한 라이브러리입니다.
• 코드 내에서 사용자로부터 배열의 크기 N을 입력받고, 이어서 N개의 정수를 입력받습니다.
• sort(A.begin(), A.end());: 배열을 정렬합니다.
• set<int> uniqueValues(A.begin(), A.end());: 정렬된 배열을 집합으로 변환하여 중복된 값을 제거합니다.
• 집합의 크기를 확인하여 두 번째로 작은 값이 있는지 판단한 후 결과를 출력합니다.

시간 복잡도

위의 알고리즘의 시간 복잡도는 다음과 같습니다:

• 정렬에 걸리는 시간: O(N log N)
• 중복 제거 및 두 번째 값 찾기: O(N) (집합의 크기를 확인하는 것은 상수 시간에 가능합니다)
• 총 시간 복잡도: O(N log N), 주로 정렬에 의한 비용입니다.

마무리

이번 강좌에서는 C++로 배열에서 두 번째로 작은 값을 찾는 방법에 대해 알아보았습니다. 주어진 배열을 정렬하고, 중복된 값을 제거하여 두 번째 최소값을 찾는 구조를 이해하셨다면, 비슷한 문제를 해결하는 데 큰 도움이 될 것입니다. 연습을 통해 다양한 배열 조작 문제를 해결해보시기 바랍니다. 수고하셨습니다!