[C] 숫자 애너그램 찾기 (다양한 정렬 알고리즘)

www.notion.so/1-53f6454e143a4d339330f0e71b381b67

✔︎ 미션 1.숫자 애너그램 찾기

✔︎ 미션 1.

1. 미션 제목

숫자 애너그램 찾기

 

2. 지시문

‘애너그램’이란 문자를 재배열하여 다른 뜻을 가진 단어로 바꾸는 것을 말합니다. 예를 들면 영어의 ‘tea’와 ‘eat’과 같이, 각 단어를 구성하는 알파벳의 구성은 같지만 뜻은 다른 두 단어를 말합니다. 우리말에는 ‘문전박대’와 ‘대박전문’과 같은 예를 들 수 있습니다. 우리는 문자 대신 숫자를 이용해서 애너그램을 찾는 프로그램을 만들어봅시다. 5자리의 숫자 1쌍이 입력으로 주어지며 애너그램일 경우에는 “True”를 아닐 경우에는 “False”를 출력하도록 합시다. 숫자를 입력 받는 부분은 따로 구현하지 않고 프로그램 내부에 배열로 선언하는 것으로 가정하고, 숫자에는 중복이 있을 수 있습니다.

예)

입력값: 12345, 54321 -> 출력값: True

입력값: 14258, 25431 -> 출력값: False

입력값: 11132, 21131 -> 출력값: True

 

3. 핵심 개념

#애너그램 #정렬알고리즘

나의 풀이

#include<stdio.h>

void swap(int*, int*);
void bubbleSort(int*, int);
void selectionSort(int*, int);
void mergeSort(int*, int, int);

int main(void) {
    //int anagram1[] = {10, 11, 13, 12, 24};
    int anagram1[] = {10, 11, 18, 8, 2};
    int anagram2[] = {2, 10, 18, 11, 8};
    int output = 0;

    bubbleSort(anagram1, 5);
    bubbleSort(anagram2, 5);
    for(int i = 0 ; i < 5; i++) {
        if(anagram1[i] != anagram2[i]) {
            output = 1;
        }
    }
    if(output == 0) printf("출력값: True\n");
    else printf("출력값: False\n");

}

void swap(int* a, int* b) {
    // 포인터를 사용하지 않으면 함수 내부에서 a와 b가 바뀐다고 하더라도
    // 함수를 빠져나오면서 원래의 배열에 변경된 내용을 저장하는 과정이 필요하다.
    // 대신 포인터를 사용하게 되면 원래의 값을 직접 바꿔줄 수 있기 때문에 코드가 더욱 간결해진다.
    int temp = *a;
    *a = *b;
    *b = temp;
}

void bubbleSort(int* nums, int length) {
    int flag = 0;   // 변경된 내용이 있는지 확인하기 위한 변수. 변경된 내용이 없다면 정렬을 종료한다.

    // j 번째 값과 j+1번째 값을 비교하기 때문에 i값을 length-1부터 시작한다.
    for(int i = length - 1 ; i > 0 ; i--) {
        for(int j = 0 ; j < i ; j++) {
            if(nums[j] > nums[j+1]) {
                swap(&nums[j], &nums[j+1]);
                flag = 1;
            }
        }
        // 변경된 내용이 없다면 정렬을 종료한다.
        if(flag == 0) return;
        flag = 0; // flag 0으로 초기화
    }
}

void selectionSort(int* nums, int length) {
    int minIndex = 0;
    // 배열의 처음부터 끝까지 진행
    for(int i = 0 ; i < length; i++) {
        // 한번 반복할 때마다 가장 작은 수가 맨 앞에 차례로 정렬되므로
        // i번째부터 배열 끝까지 가장 작은 수 검사
        for(int j = i; j < length; j++) {
            // 값을 비교할 때는 실제 저장된 값끼리 비교를 하고
            if(nums[minIndex] > nums[j]) {
                // 가장 작은 값을 저장할때는 가장 작은 값이 있는 위치를 저장한다.
                // 여기서 바로 가장 작은 값을 저장해버리면 값을 잃게된다.
                minIndex = j;
            }
        }
        // 한번 순회하면서 찾은 가장 작은 값이 있는 위치와 탐색을 시작한 위치의 값을 서로 바꿔준다
        swap(&nums[i], &nums[minIndex]);
    }
}

void mergeSort(int* nums, int start, int end) {
    // 짜보세요
}

고려사항

• 입력값1과 입력값2가 프로그램 내에 주어진다.
• 입력값은 5자리의 숫자가 주어진다.
• 입력값들의 숫자 구성이 동일한지 확인하는 문제
  • 동일하다면 True, 동일하지 않다면 False를 출력
  • 정렬을 해서 두 입력값을 비교
• 다양한 정렬 알고리즘을 적용해보자
  • bubble sort (더 빠른 버전)
  • selection sort
  • merge sort
  • 등등