[정렬 알고리즘] 숫자 애너그램 찾기

문제:

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

예)
입력값: 12345, 54321 -> 출력값: True
입력값: 14258, 25431 -> 출력값: False
입력값: 11132, 21131 -> 출력값: True

 

 

 

풀이 방법

1. 2개의 배열을 각각 오름차순으로 정렬한 후, 배열 인덱스를 차례로 하나씩 비교
2. 2개의 배열을 하나로 합친 뒤, 중복되는 배열 요소가 2개, 4개, 6개... 이런 식으로 짝수개인지 확인

 

1번 풀이:

https://sandbox.cs50.io/acdfa46b-9f8a-437d-89c3-454e5ec4b9ac

 

 

Sort 함수를 사용하여 더 깔끔한 풀이:

 

#include

//주어진 숫자열을 소트해서 결과값을 주는 함수
int* sort(int number[]);
//저 숫자열 2쌍의 소틍한 함수값이 같으면 아나그램 아니면 false 조건

int main(void)
{
int number1[5] = {1,2,3,4,5};
int number2[5] = {2,7,4,3,1};
int* sortnumber1 = sort(number1);
int* sortnumber2 = sort(number2);

for (int i = 0; i <5; i++)
{
if (sortnumber1[i] != sortnumber2[i])
{
printf("False\n");
return (0);
}
}
printf("True\n");

return 0;

}

int* sort(int number[])
{
int temp; //임시로 값 저장

for (int i = 0; i <5;i++)
{
for (int j = 0; j < 5-i-1;j++)
{
if (number[j]>number[j+1])
{
temp = number[j];
number[j] = number[j+1];
number[j+1] = temp;
}
}
}
return number;
}