[백준] 25305번 : 커트라인 | C++

1. 문제 상세

 

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

 

 

 

2. 문제 접근

 

점수들을 입력받고 점수를 내림차순으로 정렬 후 k 번째 점수를 출력하자.

 

이번에는 정렬 알고리즘에 삽입 정렬을 사용해보자.

 

■ 삽입 정렬

삽입 정렬 알고리즘은 원소를 앞쪽의 정렬된 배열의 원소들과 비교하여 

맞는 위치를 찾아 삽입하여 정렬해가는 알고리즘이다.

 

정렬의 크기가 N 이라고 할 때, 오름차순 정렬을 해보자.

2번째 원소부터 시작해 현재 원소의 왼쪽 원소들과 비교하여 원소를 맞는 위치에 삽입하며 정렬해간다.

두 번째 원소를 앞(왼쪽)의 원소인 첫 번째 원소와 비교하고, 작다면 첫 번째 원소를뒤로 밀고 첫 번째 자리에 현재 원소를 놓고, 아니면 현재 자리에 둔다.

첫 과정이 끝나면 세 번째 원소와 두 번째, 첫 번째 원소를 비교, 큰 값이 나올때 까지 비교하고

큰 값이 나오면 원소를 뒤로 밀고 해당 자리에 삽입, 아니면 현재 자리에 둔다.

이렇게 N 번째 원소까지 비교해간다.맨 앞의 원소는 자동으로 정렬되므로 이번에도 비교 횟수는 N - 1 번이 된다.

 

아래는 삽입 정렬의 예시이다.

출처 : https://gmlwjd9405.github.io/2018/05/06/algorithm-insertion-sort.html

 

 

삽입 정렬의 시간복잡도를 확인해보자.

최악의 경우, 비교 횟수는 1부터 N - 1 까지의 합이므로

이 된다.

 

최악의 경우에서 교환 횟수는 총 비교 과정의 각 단계에서 k + 2 번이 되므로

이 된다.

 

따라서 삽입 정렬의 시간복잡도는 O(N²)이다.

 

하지만 최선의 경우(이미 정렬된 배열인 경우) 교환 없이 N - 1번의 비교만 실행된다.

이 경우 시간복잡도가 O(N)이 된다.

 

삽입 정렬 또한 다른 정렬의 시간복잡도와 비교해보면 꽤 비효율적이라는 것을 볼 수 있다.

하지만 배열이 이미 정렬되어있거나, 거의 정렬된 경우 선택, 버블 정렬보다는 효율적이다.

출처 : https://gmlwjd9405.github.io/2018/05/06/algorithm-insertion-sort.html

 

 

문제풀이를 통해 선택 정렬을 구현해보자.

 

 

 

3. 문제 풀이

 

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    int n, k, a[1000], key, j;

    cin >> n >> k;

    for (int i = 0; i < n; i++) cin >> a[i];

    for (int i = 1; i < n; i++) {
        key = a[i];
        for (j = i - 1; j >= 0 && a[j] > key; j--) {
            a[j + 1] = a[j];
        }
        a[j + 1] = key;
    }

    reverse(a, a + n);

    cout << a[k - 1];
}

 

정수형 변수 n, k, key, j 와 크기가 1000인 배열 a 를 선언.

 

cin 으로 정수(점수 개수, 수상자 수)를 입력받아 각각 n, k 에 저장.

for문으로 i 가 0부터 n 보다 작을 때 1씩 더하며 반복, cin 으로 점수를 입력받아 a 의 i 번 인덱스에 저장.

 

for문으로 i 가 1부터 n 보다 작을 때 1씩 더하며 반복 // N - 1 번 비교 실행

key 에 a 의 i 번 인덱스 값을 저장 // 비교, 삽입대상 원소를 저장

다시 for문으로 j 가 i - 1 부터 0보다 크거나 같고, a 의 j 번 인덱스의 값이 key 보다 클 때 j 에 1씩 빼며 반복.

/* key 값의 앞(왼쪽)의 값들을 뒤(역순)에서부터 비교하기위한 반복 실행.

key 값(현재 삽입 대상)이 작을 때 앞의 값을 뒤로 이동시킨다.

key 값이 앞의 값보다 클 때(정렬 위치를 찾았을 때) 루프를 빠져나간다. */

a 의 j + 1 번 인덱스에 a 의 j 번 인덱스의 값을 저장. // 값을 뒤로 이동

반복이 끝나면 a 의 j + 1 번 인덱스의 값에 key 의 값을 저장한다.

// 루프를 나왔을 때(정렬 위치를 찾은 경우) 마지막으로 비교한 값 뒤에 key 값을 삽입한다.

 

모든 반복이 끝나면 reverse 함수에 a, a + n 값을 전달해 a 의 첫 번째 부터 n 번째 위치의 값을

역순으로 변경한다. // reverse 함수를 통해 정렬한 값을 오름차순 -> 내림차순으로 변경.

 

cout 으로 a 의 k - 1 번 인덱스의 값을 출력한다.

// k 번째 값을 출력. 즉 k 번째 수상자의 점수이므로 커트라인을 출력한다.

 

 

 

4. 성능 확인

 

 

 

 

5. 마무리

 

이미지 및 참고 글 출처 : https://gmlwjd9405.github.io/2018/05/06/algorithm-insertion-sort.html

 

이번에는 삽입 정렬을 사용해 보았다.