[정렬] BAEKJOON ' 2750'번, '1427'번 (C++/python)

문제 : www.acmicpc.net/problem/2750

2750번: 수 정렬하기

 

 

• 문제 해결 아이디어

    1.  단순 정렬 문제이므로 여러 정렬 방법이 사용 가능하다.

   

    2.  버블정렬과 stl을 사용하여 문제를 해결한다.

   

 

 

• python

    stl을 사용한 풀이이다.

    python에서 list sort는 O(n x lgn)을 보장하기 때문에 이 문제를 풀기에 넉넉하다.

num = int(input())
arr = list()

for _ in range(num):
    arr.append(int(input()))

arr.sort()
for i in arr:
    print(i)

 

 

• c++

    버블정렬을 이용한 풀이

    버블정렬은 시간복잡도가 O(n²)이지만 이 문제는 N이 최대 1000이고, 시간 제한이 1초이므로, 충분하다.

#include "iostream"

using namespace std;

int main(){
    
    int num;
    cin >> num;
    int arr[num];
    for(int i=0 ; i< num ; i++){
        cin >> arr[i];
    }
    for(int i=1 ; i< num ; i++){
        for(int j=0 ; j< num-i ; j++){
            if(arr[j] > arr[j+1]){
                int tmp;
                tmp = arr[j+1];
                arr[j+1] = arr[j];
                arr[j] = tmp;
            }
        }
    }
    for(int i=0 ; i< num ; i++){
        printf("%d\n",arr[i]);
    }
}

 

 

    stl을 이용한 풀이.

    c++에서 sort함수 또한 O(n x lgn)을 보장해준다.

#include "iostream"
#include "algorithm"

using namespace std;

int main(){
    
    int num;
    
    cin >> num;
    int elements[num];
    
    for(int i=0 ; i< num ; i++){
        cin >> elements[i];
    }
    sort(elements,elements+num);
    for(int i=0 ; i< num ; i++){
        printf("%d\n",elements[i]);
    }
}

 

 

 

 

 

 

 

문제 : www.acmicpc.net/problem/1427

1427번: 소트인사이드

 

• 문제 해결 아이디어

    1.  입력받은 배열은 수 이므로 0~9중 하나이다.

 

    2.  9부터 0까지 순회하며 각 수가 나올 떄 마다 해당 수를 출력해주면 자동으로 정렬이 가능하다.

 

 

 

• python

array = input()

for i in range(9,-1,-1):    # 역행을 나타내기위한 방법
    for j in array:       
        if int(j) == i:     # i와 같은 수가 나올 때 마다 출력해준다.
            print(i, end='')

 

 

• c++

    초기에 counting sort를 이용하여 문제를 해결하려 하였다.

    counting sort에 대한 내용은 knowable.tistory.com/17에서 확인할 수 있다.

 

 

#include "iostream"
#include "string"

#define max 1000000000

using namespace std;

int A[max]={0,};
int B[10]={0,};
int result[max]={0,};

int main(){
    
    string num;
    
    cin >> num;
 
    int len = num.length();
    
    
    for(int i=0 ; i< len ; i++){      // 문자열을 이루고있는 숫자를 count해준다.
        int tmp = num.at(i)-48;
        A[i] = tmp;
        B[tmp]++;
    }
    for(int i=0 ; i< 10 ; i++){       // B배열을 누적 배열로 만들어준다.
        B[i+1] += B[i];
    }
    for(int i= len-1 ; i>= 0 ; i--){  // result배열에 결과를 써주고, B배열의 요소를 1 감소시킨다.

        result[B[A[i]]] = A[i];
        B[A[i]]--;
        
    }
    for(int i=len ; i>= 1 ; i--){
        printf("%d",result[i]);
    }
    printf("\n");
    
    return 0;
    
}

 

 

이는 n이 입력되었을 때, 문자열을 count해주는 부분에서 O(n) , result에 결과를 저장하는 부분에서 O(n), 출력부분에서 O(n)이 소요되어

Linear time( O(n) ) 안에 정렬을 끝낼 수 있지만, 애초에 n이 최대 10억이기 때문에, 이를 다 저장할 수 있는 배열을 선언할 수 없고 컴파일 에러가 나게된다. 

 

알고리즘의 B배열에 count값이 모두 저장되어있음을 이용하여, 위  '문제 해결 아이디어' 에서 언급한 것 처럼 각 수가 출현한 개수대로

출력하였다.

 

#include "iostream"
#include "string"

using namespace std;

int B[10]={0,};

int main(){
    
    string num;
    cin >> num;
 
    int len = num.length();
    
    for(int i=0 ; i< len ; i++){
        int tmp = num.at(i)-48;
        B[tmp]++;
    }
    
    for(int i=9 ; i>= 0 ; i--){
        for(int j=0 ; j< B[i] ; j++)
            printf("%d",i);
    }
    
    printf("\n");
    
    return 0; 
}