[백준] 2750번 수 정렬하기 C++ 문제 풀이 정렬

문제

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.

출력

첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

---

예제 입력1

5

5

2

3

4

1

---

예제 출력1

1

2

3

4

5

---

문제 풀이

#include <iostream>
using namespace std;
int main(void){
    int N, temp;
    cin>>N;
    int arr[N];
    for(int i = 0; i < N; i++){
        cin>>arr[i];
    }

    for(int j = 0; j < N-1; j++)
        for(int k = j+1; k < N; k++){
            if(arr[j] > arr[k]){
                temp = arr[k];
                arr[k] = arr[j];
                arr[j] = temp;
            }
        }
    
    for(int l = 0; l < N; l++){
        if(l + 1 < N && arr[l] == arr[l+1])
            continue;
        cout << arr[l] << endl;
    }
}

시간 복잡도가 O(n²)인 정렬 알고리즘으로 풀 수 있기 때문에

선택 정렬로 구현하여 문제를 풀었습니다.

선택 정렬은 정렬하여 값을 넣을 위치를 정해놓고 비교를 하는 알고리즘입니다.

 

배열의 첫 번째나 맨 끝에서부터 순차적으로 정렬되며, 문제에서는 오름차순으로 정렬하기 때문에

저는 배열의 첫 번째 원소부터 정렬했습니다.

arr[j]의 값이 arr[k]보다 크다면 둘의 위치를 바꿉니다.

결과적으로 arr[j]에는 가장 작은 값이 정렬됩니다.

arr[0]에는 가장 작은 값, arr[1]에는 그다음으로 가장 작은 값, ... 이렇게 정렬되는 구조입니다. 

 

중복되지 않게 출력해야 하므로 마지막에 현재 원소와 다음 원소의 값이 같으면 출력을 건너 뛰었습니다.

 

 

 

 

출처 : https://www.acmicpc.net/problem/2750

2750번: 수 정렬하기