[C#] 25305번: 커트라인

목차

---

백준 단계별로 풀어보기

25.10.17

13단계: 정렬

25305번: 커트라인

문제 링크 : https://www.acmicpc.net/problem/25305

 

문제 풀이

>> 문제를 풀기 위해 알아야 할 개념

- 선택 정렬(Selection Sort)

: 1번째 원소부터 끝까지 훑어서 가장 작은 게 1번째 원소, 그 다음엔 2번째 원소부터 끝까지 훑어서 가장 작은게 2번째 원소와 같은 방식으로 (n - 1)번 반복하여 정렬한다.

• 어떻게 정렬이 되어 있든 일관성 있게 n(n - 1) / 2 에 비례하는 시간이 걸린다.
• 버블 정렬에 비해 두 배 정도 빠르다.

 

- 코드

for (int i = 0; i < arr.Length - 1; i++)
{
    int minIndex = i;
    for (int j = i + 1; j < arr.Length; j++)
    {
        if (arr[j] < arr[minIndex])
            minIndex = j;
    }
    (arr[i], arr[minIndex]) = (arr[minIndex], arr[i]);
}

 

※ 이해를 위한 영상

출처 : 나무위키 - 정렬 알고리즘

 

>> 풀이

1. 입력값을 받아 int값으로 변환하여 응시자 수를 담을 변수 count 와 상을 받는 사람의 수를 담을 변수 cutoff 에 대입하고, 학생들의 점수를 담을 int형 배열 arr 를 초기화한다.
2. 각 학생의 점수를 입력받아서 for 반복문을 통해 배열 arr 에 담는다.
3. 선택 정렬을 활용하여 arr 에 있는 값을 오름차순으로 정렬한다.
4. 오름차순으로 정렬했기 때문에 뒤에서부터 커트라인만큼 뺀 index의 값을 출력한다.

 

정답 코드

class Backjoon
{
    static void Main(string[] args)
    {
        string[] input = Console.ReadLine().Split();
        int count = int.Parse(input[0]);
        int cutoff = int.Parse(input[1]);
        int[] arr = new int[count];
        
        string[] scores = Console.ReadLine().Split();
        for (int i = 0; i < count; i++)
        {
            arr[i] = int.Parse(scores[i]);
        }

        for (int i = 0; i < arr.Length - 1; i++)
        {
            int minIndex = i;
            for (int j = i + 1; j < arr.Length; j++)
            {
                if (arr[j] < arr[minIndex])
                    minIndex = j;
            }
            (arr[i], arr[minIndex]) = (arr[minIndex], arr[i]);
        }
        
        Console.Write(arr[arr.Length - cutoff]);
    }
}