[백준알고리즘]2750번 수 정렬하기 C++, Python

문제

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

입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다.

이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.

출력

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

 

---

N개의 수가 주어졌을 때 오름차순으로 정렬하는 프로그램을 작성해야 한다.

5개를 입력하겠다고 처음으로 5를 입력한다.

5개의 수를 입력하고 N개의 수가 오름차순으로 정렬하는 프로그램이다.

이때 시간 복잡도가 O(n^2)인 정렬 알고리즘으로 풀 수 있다고 한다.

어떻게 풀어야 할 지 생각이 필요할 듯 하다.

중복은 없으니 좀 편할 듯 하다.

---

https://gmlwjd9405.github.io/2018/05/06/algorithm-bubble-sort.html

[알고리즘] 버블 정렬(bubble sort)이란 - Heee's Development Blog

일단 버블 정렬로 풀도록 한다.

삽입 정렬은 좀 번거로울 것 같아 버블 정렬로 결정했다.

버블 정렬은 위의 설명을 보면 더욱 이해가 잘 될 듯 하다.

 

---

 

C++

코드 설명부터 보도록 한다.

문제에 의하면 개수는 1~1000이었다.

따라서 배열을 1001의 크기를 갖도록 한다.

 

num을 입력 받고, num만큼 arr[i]를 입력 받는다.

 

swap함수를 사용해도 되지만 그냥 함수 내용을 바로 써도 될 듯 했다.

그래서 swap내용을 중첩된 for문 안에 사용했다.

1번째가 작은거, 2번째가 1번째보단 큰 거,,,이런 식으로 점점 값이 커져야 한다.

그래서 [j]가 [j+1]보다 클 때 swap하도록 한다.

 

for문을 통해 정렬한 arr[i]를 출력하면 된다.

#include <iostream>
using namespace std;

int main(){
    int arr[1001];
    int num;
    
    cin>>num;
    
    for(int i=0;i<num;i++){
        cin>>arr[i];
    }
    
    int temp=0;
    
    for(int i=0;i<num;i++){
        for(int j=0;j<num-i-1;j++){
            if(arr[j]>arr[j+1]){
                temp=arr[j+1];
                arr[j+1]=arr[j];
                arr[j]=temp;
            }
        }
    }
    
    for(int i=0;i<num;i++){
        cout<<arr[i]<<endl;
    }
    return 0;
}

 

Python

 

num = int(input())
arr = []

for i in range(num):
    arr.append(int(input()))
arr=sorted(arr)

for i in range(len(arr)):
    print(arr[i])