본문 바로가기
Baekjoon/단계별로 풀어보기

[단계12] 정렬 (9문제)

by 해적거북 2021. 1. 14.
728x90

www.acmicpc.net/step/9

 

정렬 단계

시간 복잡도가 O(nlogn)인 정렬 알고리즘으로 풀 수 있습니다. 예를 들면 병합 정렬, 힙 정렬 등이 있지만, 어려운 알고리즘이므로 지금은 언어에 내장된 정렬 함수를 쓰는 것을 추천드립니다.

www.acmicpc.net

 

● [문제번호 2750] 수 정렬하기

#include <stdio.h>
#include <stdlib.h>

void swap(int* num, int a, int b)
{
    int temp = num[a];
    num[a] = num[b];
    num[b] = temp;
}

int main()
{
    int N;
    scanf("%d", &N);
    
    int* num = (int*)malloc(N * sizeof(int));
    
    for(int i = 0; i < N; i++)
        scanf("%d", &num[i]);
    
    // 버블 정렬
    for(int i = 0; i < N - 1; i++)
        for(int j = 0; j < N - i - 1; j++)
            if(num[j] > num[j + 1])
                swap(num, j, j + 1);
    
    for(int i = 0; i < N; i++)
        printf("%d\n", num[i]);
    
    free(num);

    return 0;
}

 

● [문제번호 2751] 수 정렬하기 2

#include <stdio.h>
#include <stdlib.h>

void merge(int* num, int left, int mid, int right)
{
    int l = left;
    int r = mid + 1;
    
    // 분할 된 배열의 수를 잘 생각해야함
    int* temp = (int*)malloc((right - left + 1) * sizeof(int));
    int t = 0;
    
    // 한 쪽이라도 다 끝날때 까지 병합
    while(l <= mid && r <= right)
    {
        if(num[l] < num[r])
        {
            temp[t] = num[l];
            l++;
        }
        else
        {
            temp[t] = num[r];
            r++;
        }
        
        t++;
    }
    
    // 왼쪽 남은 경우
    while(l <= mid)
    {
        temp[t] = num[l];
        l++;
        t++;
    }
    
    // 오른쪽 남은 경우
    while(r <= right)
    {
        temp[t] = num[r];
        r++;
        t++;
    }

    t = 0;
    for(int i = left; i <= right; i++, t++)
        num[i] = temp[t];
    
    free(temp);
    
    return;
}

// Divide and Conquer
void mergeSort(int* num, int left, int right)
{
    if(left < right)
    {
        int mid = (left + right) / 2;
        
        // 반으로 계속 나누기
        mergeSort(num, left, mid);
        mergeSort(num, mid + 1, right);
        
        // 정렬하여 합치기
        merge(num, left, mid, right);
    }
}

int main()
{
    int N;
    scanf("%d", &N);
    
    int* num = (int*)malloc(N * sizeof(int));
    
    // 입력
    for(int i = 0; i < N; i++)
        scanf("%d", &num[i]);
    
    // 합병 정렬
    mergeSort(num, 0, N - 1);
    
    // 출력
    for(int i = 0; i < N; i++)
        printf("%d\n", num[i]);
    
    free(num);

    return 0;
}

 

● [문제번호 10989] 수 정렬하기 3

#include <stdio.h>

int main()
{
    int N;
    scanf("%d", &N);
    
    // 카운팅 배열
    int count[10001] = {0, };
    
    // 입력
    for(int i = 0; i < N; i++)
    {
        int temp;
        scanf("%d", &temp);
        count[temp]++;
    }
    
    // 카운트한 수 만큼씩 인덱스 출력
    for(int i = 1; i < 10001; i++)
        while(count[i] != 0)
        {
            printf("%d\n", i);
            count[i]--;
        }
    
    return 0;
}

 

● [문제번호 2108] 통계학

#include <stdio.h>

int main()
{
    int N;
    scanf("%d", &N);
    
    int total = 0, avg;
    int mid;
    int count[8001] = {0, };
    int countmax1 = 0, countmax2 = 0, countmax1_index;
    int max = 0, min = 0, range;
    
    for(int i = 0; i < N; i++)
    {
        int temp;
        scanf("%d", &temp);
        
        total += temp;
        
        count[temp + 4000]++;
        
        if(i == 0)
        {
            max = temp;
            min = temp;
        }
        else
        {
            if(max < temp)
                max = temp;
            
            if(min > temp)
                min = temp;
        }
    }
    
    // 산술평균
    if(total < 0)
    {
        total *= -1;
        if(total % N > N / 2)
            printf("-%d\n", total / N + 1);
        else
            printf("-%d\n", total / N);
    }
    else
    {
        if(total % N > N / 2)
            printf("%d\n", total / N + 1);
        else
            printf("%d\n", total / N);
    }
    
    // 중앙값
    int temp = 0;
    for(int i = 0 ; i < 8001; i++)
    {
        temp += count[i];
        if(temp >= N / 2 + 1)
        {
            printf("%d\n", i - 4000);
            break;
        }
    }
    
    // 최빈값
    for(int i = 0; i < 8001; i++)
    {
        if(countmax1 < count[i])
        {
            countmax2 = countmax1;
            countmax1 = count[i];
            countmax1_index = i;
        }
        else if(countmax2 < count[i])
            countmax2 = count[i];
    }
    
    if(countmax1 > countmax2)
        printf("%d\n", countmax1_index - 4000);
    else if(countmax1 == countmax2)
    {
        int flag = 0;
        for(int i = 0; i < 8001; i++)
            if(flag == 0 && count[i] == countmax1)
                flag = 1;
            else if(flag == 1 && count[i] == countmax1)
            {
                printf("%d\n", i - 4000);
                break;
            }
    }
    
    // 범위
    printf("%d\n", max - min);
    return 0;
}

// 수를 저장하지 않고 계산해서 푸는 방법

 

● [문제번호 1427] 소트인사이드

#include <stdio.h>

int main()
{
    int N[10] = {0, };
    
    // 각 자리별 숫자의 갯수를 파악
    while(1)
    {
        char temp;
        scanf("%c", &temp);
        
        if(!('0' <= temp && temp <= '9'))
            break;
        
        N[temp - '0']++;
    }
    
    // 9부터 갯수만큼 출력
    for(int i = 9; i >= 0; i--)
    {
        if(N[i] == 0)
            continue;
        
        for(int j = 0; j < N[i]; j++)
            printf("%d", i);
    }
    return 0;
}

// 위의 계수 정렬로 부터 영감을 얻어 구현함

 

● [문제번호 11650] 좌표 정렬하기

#include <stdio.h>
#include <stdlib.h>

void merge(int* x, int* y, int left, int mid, int right)
{
    int l = left;
    int r = mid + 1;
    
    int* sortedX = (int*)malloc((right - left + 1) * sizeof(int));
    int* sortedY = (int*)malloc((right - left + 1) * sizeof(int));
    
    int index = 0;
    while(l <= mid && r <= right)
    {
        if(x[l] < x[r])
        {
            sortedX[index] = x[l];
            sortedY[index] = y[l];
            l++;
        }
        else if(x[l] == x[r])
        {
            if(y[l] < y[r])
            {
                sortedX[index] = x[l];
                sortedY[index] = y[l];
                l++;
            }
            else
            {
                sortedX[index] = x[r];
                sortedY[index] = y[r];
                r++;
            }
        }
        else
        {
            sortedX[index] = x[r];
            sortedY[index] = y[r];
            r++;
        }
        
        index++;
    }
    
    while(l <= mid)
    {
        sortedX[index] = x[l];
        sortedY[index] = y[l];
        l++;
        index++;
    }
    
    while(r <= right)
    {
        sortedX[index] = x[r];
        sortedY[index] = y[r];
        r++;
        index++;
    }
    
    index = 0;
    for(int i = left; i <= right; i++, index++)
    {
        x[i] = sortedX[index];
        y[i] = sortedY[index];
    }
    
    free(sortedX);
    free(sortedY);
}

void mergeSort(int* x, int* y, int left, int right)
{
    if(left < right)
    {
        int mid = (left + right) / 2;
        mergeSort(x, y, left, mid);
        mergeSort(x, y, mid + 1, right);
        
        merge(x, y, left, mid, right);
    }
}

int main()
{
    int N;
    scanf("%d", &N);
    
    int* x = (int*)malloc(N * sizeof(int));
    int* y = (int*)malloc(N * sizeof(int));
    
    for(int i = 0; i < N; i++)
        scanf("%d %d", &x[i], &y[i]);
    
    // 합병정렬 이용
    mergeSort(x, y, 0, N - 1);
    
    for(int i = 0; i < N; i++)
        printf("%d %d\n", x[i], y[i]);
    
    free(x);
    free(y);
    
    return 0;
}

// 버블정렬 이용시 시간 초과

 

● [문제번호 11651] 좌표 정렬하기 2

#include <stdio.h>
#include <stdlib.h>

void merge(int* x, int* y, int left, int mid, int right)
{
    int l = left;
    int r = mid + 1;
    
    int* sortedX = (int*)malloc((right - left + 1) * sizeof(int));
    int* sortedY = (int*)malloc((right - left + 1) * sizeof(int));
    
    int index = 0;
    while(l <= mid && r <= right)
    {
        if(y[l] < y[r])
        {
            sortedX[index] = x[l];
            sortedY[index] = y[l];
            l++;
        }
        else if(y[l] == y[r])
        {
            if(x[l] < x[r])
            {
                sortedX[index] = x[l];
                sortedY[index] = y[l];
                l++;
            }
            else
            {
                sortedX[index] = x[r];
                sortedY[index] = y[r];
                r++;
            }
        }
        else
        {
            sortedX[index] = x[r];
            sortedY[index] = y[r];
            r++;
        }
        
        index++;
    }
    
    while(l <= mid)
    {
        sortedX[index] = x[l];
        sortedY[index] = y[l];
        l++;
        index++;
    }
    
    while(r <= right)
    {
        sortedX[index] = x[r];
        sortedY[index] = y[r];
        r++;
        index++;
    }
    
    index = 0;
    for(int i = left; i <= right; i++, index++)
    {
        x[i] = sortedX[index];
        y[i] = sortedY[index];
    }
    
    free(sortedX);
    free(sortedY);
}

void mergeSort(int* x, int* y, int left, int right)
{
    if(left < right)
    {
        int mid = (left + right) / 2;
        mergeSort(x, y, left, mid);
        mergeSort(x, y, mid + 1, right);
        
        merge(x, y, left, mid, right);
    }
}

int main()
{
    int N;
    scanf("%d", &N);
    
    int* x = (int*)malloc(N * sizeof(int));
    int* y = (int*)malloc(N * sizeof(int));
    
    for(int i = 0; i < N; i++)
        scanf("%d %d", &x[i], &y[i]);
    
    // 합병정렬 이용
    mergeSort(x, y, 0, N - 1);
    
    for(int i = 0; i < N; i++)
        printf("%d %d\n", x[i], y[i]);
    
    free(x);
    free(y);
    
    return 0;
}

// 버블정렬 이용시 시간 초과
// 위 문제에서 x[] <-> y[] 교환만 함

 

● [문제번호 1181] 단어 정렬

#include <stdio.h>
#include <string.h>

void swap(char* a, char* b)
{
    char temp[51];
    strcpy(temp, a);
    strcpy(a, b);
    strcpy(b, temp);
}

void quickSort(char (*str)[51], int left, int right)
{
    int l = left;
    int r = right;
    
    char pivot[51];
    strcpy(pivot, str[(left + right) / 2]);
    int pivotLen = strlen(pivot);
    
    do
    {
        while(1)
        {
            if(pivotLen > strlen(str[l]))
                l++;
            else if(pivotLen == strlen(str[l]))
                if(strcmp(pivot, str[l]) > 0)
                    l++;
                else
                    break;
            else
                break;
        }
        
        while(1)
        {
            if(pivotLen < strlen(str[r]))
                r--;
            else if(pivotLen == strlen(str[r]))
                if(strcmp(pivot, str[r]) < 0)
                    r--;
                else
                    break;
            else
                break;
        }
        
        if(l <= r)
        {
            swap(str[l], str[r]);
            l++;
            r--;
        }
        
    }while(l <= r);
    
    if(left < r)
        quickSort(str, left, r);
    
    if(l < right)
        quickSort(str, l, right);
    
}

int main()
{
    int N;
    scanf("%d", &N);
    
    char str[20000][51];
    
    for(int i = 0; i < N; i++)
        scanf("%s", str[i]);
    
    quickSort(str, 0, N - 1);
    
    for(int i = 0; i < N - 1; i++)
        if(strcmp(str[i], str[i + 1]) != 0)
            printf("%s\n", str[i]);
    
    if(str[N - 2] != str[N - 1])
        printf("%s\n", str[N - 1]);
    
    return 0;
}

 

● [문제번호 10814] 나이순 정렬

#include <stdio.h>
#include <stdlib.h>

typedef struct
{
    int age;
    char name[101];
}Student;

void merge(Student* student, Student* sorted, int left, int mid, int right)
{
    int l = left;
    int r = mid + 1;
    int s = left;
    
    while(l <= mid && r <= right)
        if((student + l)->age <= (student + r)->age)
            sorted[s++] = student[l++];
        else
            sorted[s++] = student[r++];
    if(l <= mid)
        while(l <= mid)
            sorted[s++] = student[l++];
    else
        while(r <= right)
            sorted[s++] = student[r++];
        
    for(int t = left; t <= right; t++)
        student[t] = sorted[t];
}

void mergeSort(Student* student, Student* sorted, int left, int right)
{
    if(left < right)
    {
        int mid = (left + right) / 2;
        
        mergeSort(student, sorted, left, mid);
        mergeSort(student, sorted, mid + 1, right);
        merge(student, sorted, left, mid, right);
    }
}

int main()
{
    int N;
    scanf("%d", &N);
    
    Student* student = (Student*)malloc(N * sizeof(Student));
    Student* sorted = (Student*)malloc(N * sizeof(Student));
    
    for(int i = 0; i < N; i++)
        scanf("%d %s", &(student + i)->age, (student + i)->name);
    
    mergeSort(student, sorted, 0, N - 1);
    
    for(int i = 0; i < N; i++)
        printf("%d %s\n", (student + i)->age, (student + i)->name);
    
    free(sorted);
    free(student);
    
    return 0;
}

// 정렬 조건 중에 동일 나이라면 입력 순서라서
// 퀵정렬 말고 병합 정렬을 이용함
728x90
저작자표시

'Baekjoon > 단계별로 풀어보기' 카테고리의 다른 글

[단계 13] 백트래킹 (8문제)  (0) 2021.01.22
[단계11] 부르트 포스 (5문제)  (0) 2021.01.13
[단계10] 재귀 (4문제)  (0) 2021.01.12
[단계09] 기본 수학2 (11문제)  (0) 2021.01.09
[단계08] 기본 수학1 (9문제)  (0) 2020.12.20
[단계07] 문자열 (10문제)  (0) 2020.12.20
[단계06] 함수 (3문제)  (0) 2020.12.18

관련글

댓글

티스토리툴바