[C#] 2587번: 대표값2

목차

---

백준 단계별로 풀어보기

25.10.16

13단계: 정렬

2587번: 대표값2

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

 

문제 풀이

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

- 삽입 정렬(Insertion Sort)

: k번째 원소를 1부터 k-1까지와 비교해 적절한 위치에 끼워넣고 그 뒤의 자료를 한 칸씩 뒤로 밀어내는 방식으로 정렬한다.

• 시간 복잡도 O(n²)의 정렬들 중 빠른 편이나, 자료구조에 따라선 뒤로 밀어내는데 걸리는 시간이 크다.
• 이미 정렬되어 있는 자료구조에 자료를 하나씩 삽입/제거하는 경우에는 최고의 정렬 알고리즘이 되는데, 탐색을 제외한 오버헤드가 매우 적기 때문이다.
• 배열이 작을 경우에 상당히 효율적이다.

 

- 코드

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

 

※ 이해를 위한 영상

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

 

>> 풀이

1. 다섯 개의 자연수를 담을 int형 배열 arr 을 초기화하고 평균을 구하기 위해 자연수의 합을 담을 변수 sum 을 선언한다.
2. for 반복문을 통해 입력값을 int값으로 변환하여 arr 에 담고 sum 에 입력값을 더해준다.
3. 삽입 정렬을 활용하여 arr 에 있는 값을 오름차순으로 정렬한다.
4. 평균과 중앙값을 출력한다.

 

정답 코드

class Backjoon
{
    static void Main(string[] args)
    {
        int[] arr = new int[5];
        int sum = 0;

        for (int i = 0; i < 5; i++)
        {
            arr[i] = int.Parse(Console.ReadLine());
            sum += arr[i];
        }

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

        Console.WriteLine(sum / 5);
        Console.Write(arr[2]);
    }
}