C 배열 중복 숫자 개수 - C baeyeol jungbog susja gaesu

C언어의 정수가 저장된 배열 혹은 문자열에서 2번 이상 등장한 값들의 목록을 찾는 방법과

중복을 제거하여 고유값만 남기는 방법에 대해서 다루어보도록 하겠습니다.

숫자(정수) 배열 내 중복 원소 찾기

가정 : 배열 a 내에는 0~n까지의 범위 내에서 정수가 등장할 수 있습니다.

풀이법 : n+1 사이즈의 등장 횟수 배열 check를 선언 후, a 배열의 원소를 순회하며

각 인덱스에 해당 숫자의 등장 횟수를 카운팅하고, 2 이상인 인덱스들만을 모아서 반환합니다.

0~4 범위에서 정수가 등장할 수 있는 경우의 간단한 예제에 대한 원리는

다음 그림처럼 표현할 수 있습니다.

해당 예제의 실제 C언어 구현 코드는 아래와 같습니다.(각 줄 코드의 설명은 주석을 참고하세요!)

#include <stdio.h>

int main(){

// 중복 여부를 탐색할 배열 a
int a[] = {3, 1, 2, 1, 0, 4, 1, 2, 4};
int size_a = sizeof(a) / sizeof(int); // 배열 a의 길이

// 각 원소의 등장 횟수를 저장할 배열 check
int check[5] = {};

// a를 순회하며 check에 등장 횟수 저장
int idx;
for(int i = 0; i < size_a; i++){
  idx = a[i];
  check[idx]++;
}

// check의 값을 검사하여 2회 이상 등장한 원소만 출력
printf("중복된 원소 : ");
for(int i = 0; i < 5; i++){
  if(check[i] >= 2) printf("%d ", i);
}

}

위 코드 실행 시, 출력 결과로 "중복된 원소 : 1 2 4 "라고 등장하게 됩니다.

마찬가지 원리로 k회 이상 등장한 원소들만을 골라서 출력하는 것도 가능하며,

위 알고리즘의 시간 복잡도는 배열 a 원소의 개수 n에 비례하는 O(n)입니다.

문자열 내 중복 원소 찾기

위의 문제를 확장하여 문자열 내에서 2회 이상 등장한 글자를 찾는 것도 가능합니다.

참고로, 문자열에서 등장 가능한 char의 종류는 총 128가지이므로,

위 예제에서 check의 크기를 128로 정하고, 해당 문자가 지정된 아스키 코드 번호를

인덱스로 삼아 문자열을 순회하면서 같은 원리를 적용해주시면 됩니다.

구현 코드의 예시는 아래와 같습니다.(숫자 배열의 예제와 다른 부분을 찾아보세요!)

#include <stdio.h>

int main(){

// 중복 여부를 탐색할 문자열 a
char a[] = "abc!cdk!?";
int size_a = sizeof(a) / sizeof(char); // 문자열 a의 길이

// 각 원소의 등장 횟수를 저장할 배열 check
int check[128] = {};

// a를 순회하며 check에 등장 횟수 저장
int idx;
for(int i = 0; i < size_a; i++){
  idx = a[i];
  check[idx]++;
}

// check의 값을 검사하여 2회 이상 등장한 원소만 출력
printf("중복된 원소 : ");
for(int i = 0; i < 128; i++){
  if(check[i] >= 2) printf("%c ", i);
}

}

코드를 실행하면 "중복된 원소 : ! c "가 출력됩니다.

중복이 제거된 고유값 배열 반환

같은 원리를 활용하여 check 배열 내에서 1이상의 값이 저장된 인덱스들만 가져와

중복이 제거된 고유값들이 저장된 배열을 반환받는 것도 가능합니다.

여기서는 고유값들만 저장할 새로운 배열의 선언이 필요합니다.

(해당 배열의 이름을 unique로 가정하겠습니다.)

배열 a 내에서 0~9까지의 정수가 등장할 수 있는 상황을 가정한 예시의 코드는 아래와 같습니다.

#include <stdio.h>

int main(){

// 중복 여부를 탐색할 배열 a
int a[] = {9, 3, 3, 1, 1, 5, 1, 7};
int size_a = sizeof(a) / sizeof(int); // 배열 a의 길이

// 각 원소의 등장 횟수를 저장할 배열 check
int check[10] = {};

// a를 순회하며 check에 등장 횟수 저장
int idx;
for(int i = 0; i < size_a; i++){
  idx = a[i];
  check[idx]++;
}

// 고유값들을 모아서 저장할 배열 unique 선언
int unique[10] = {};

// check의 값을 검사하여 1회 이상 등장한 원소만 unique에 저장
int unique_cnt = 0; // 고유값 개수 저장
for(int i = 0; i < 10; i++){
  if(check[i] >= 1) unique[unique_cnt++] = i;
}

// 배열 원소 출력(고유값 개수 위치까지만 출력하여 뒤의 0 출력 방지)
for(int i = 0; i < unique_cnt; i++){
  printf("%d ", unique[i]);
}
  
}

출력 결과는 "1 3 5 7 9 "로 등장한 적이 있는 원소들만 모아서 배열에 저장된 것을

확인할 수 있습니다.

배열의 데이터를 처리하는 프로그램을 만드는 연습문제입니다.

하....갈수록 어려워지네요ㅠㅠ

근대 뭐 아직까진... 조금만 더 생각하면 이해가 가는 부분들이였는데

벌써부터 포인터압박이...ㅋㅋㅋ 쨋든 하나씩 살펴보죠!^^

이렇게 총 세 문제인데요.

첫번째 문제는 1부터 20까지 숫자로만 초기화된 ary 배열을 위에 사진과 같이 선언하고,

이 배열에서 특정 숫자의 개수를 세어 출력하는 프로그램이에요.

이 문제 만큼은.. 혼자힘으로 풀었어요!^^

아!!!그리고 오늘부턴...소스코드로 포스팅할께요~~~^.*

입력받은 no의 값과 ary배열중에 같은 요소를 찾아 res값을 하나씩 증가 시키는 프로그램이였어요.

두번째 문제는 위의 문제에서 1부터 20까지 모든 숫자에 대해서 개수를 세어 출력하는 문제인데요.

각 숫자에 대하여 개수를 누력시킬 변수들을 배열로 선언하여 작성하라네요.

위에 또 힌트를 준게... int count[20]={0};  이렇게 각 요소들을 전부 0으로 초기화시켰어요.

이게.. 왜 가능한지는 전 포스팅에서 설명드렸던건데요.

배열요소의 수보다 초기화 값이 적으면 남은 기억공간은 모두 0으로 채워진다는 자동기능 때문이에요.

정확히 말하자면 count[0]의 값은 0으로 저장된거고, 초기화 되지 않은 나머지 요소들은 자동으로 0으로 채워진거구요.

풀이를 보면서 하나씩 살펴볼게요.

음...

1.  for(i=1; i<=20; i++){
2.         for(j=0; j<size; j++){
3.             if(ary[j]==i) count[i-1]++;
4.         }
5.     }

제가 이부분이 좀.. 막혔어가지고....

일단 살펴봅시다!

for(i=1; i<=20; i++)  1부터 20까지의 숫자를 찾는 for문인데요.

이 값은..단순히 ary배열에 초기화된 값들이 1부터 20까지의 숫자들이 있어서 지정된 범위라고 생각하시면 되요.

이 for문 부터 시작해야 1부터 20까지의 범위가 잡힌 숫자 중에 ary배열에 초기화된 값들과 같은 배열요소들을 찾겟죠?

그다음이 for(j=0; j<size; j++) {

if(ary[j]==i) count[i-1]++;

}                                          여기까지인데요.

맨 위에 for문에서 1~20이 1부터 차례대로 내려오고

여기 있는 for문이 ary배열을 sizeof로부터 배열요소의 개수를 구한 만큼 반복하면서 

if문에서 초기화된 ary배열요소들과 만나 그 같이 같으면

0으로 초기화 되있는 해당요소 count배열의 값들을 하나씩 증가시킵니다.

여기서 count[i]가 아닌 count[i-1]인 이유는

배열의 첨자는 0부터 시작하는데 위의 for문에서 반복 제어변수 i가 1부터 시작하고 있으니깐

i-1로 시작해야 첨자가 0부터 순차적으로 저장이 되겠죠?

다소...복잡하지만 하나하나 잘 뜯어 보면 그다지 어렵지 않았네요!^^

마지막으로 세번째문제는....

배열에 임의의 숫자를 초기화한 후에 각 숫자들의 위치를 반대로 바꾸는 프로그램을 작성하는 건데요.

배열은 하나만 사용하고, 배열의 크기가 바뀌더라도 수정할 필요가 없도록 작성하라네요.

이것도 위에 사진보시면 

첫번째랑 마지막이랑 바꾸고 두번째랑 네번째랑 바꾸라는 것과

두 변수의 값을 바꾸기 위해서 임시변수도 하나 준비하라는 힌트를 줬네요.

1. #include <stdio.h>
2.  
3. int main()
4. {
5.     int ary[]={1,2,3,4,       //배열의 선언과 초기화
6.     int i, r;                 //r은 배열에서 왼쪽의 값과 교환할 오른쪽 값의 위치를 저장
7.     int temp;                 //두 값을 교환할 때 사용할 임시변수
8.     int size;                 //배열요소의 개수를 저장할 변수
9.                                
10.     size = sizeof(ary)/sizeof(ary[0]);         //배열요소의 개수를 구했어요.
11.  
12.     for(i=0; i<size; i++){                      //우선 바뀌기 전의 배열의 값을 출력하구요.
13.         printf("%3d", ary[i]);
14.     }
15.  
16.     for(i=0; i<size/2; i++){                //바꾸는 횟수는 배열요소의 개수의 절반이겠죠?
17.         r=size-1-i;                         //왼쪽 값과 교환할 오른쪽 값의 위치를 계산합니다.
18.         temp=ary[i];                        //두 배열요소의 값을 교환하구요.
19.         ary[i]=ary[r];
20.         ary[r]=temp;
21.     }
22.  
23.     printf(" 바뀐 배열에 저장한 값 : ");
24.     for(i=0; i<size; i++){
25.         printf("%3d", ary[i]);
26.     }
27.     return 0;
28. }

한번더 설명드리면

for(i=0; i<size/2; i++){

r=size-1-i;

temp=ary[i];

ary[i]=ary[r];

ary[r]=temp;

}

우선 

ary[0]=1;

ary[1]=2;

ary[2]=3;

ary[3]=4;

ary[4]=5;

이 경우에는 배열요소가 1,2,3,4,5 총 다섯개로 size가 5가 되겠죠? 

이런 배열요소의 순서를 5,4,3,2,1 이런식으로 바꾸라는건데

1이랑5랑 바꾸고 2랑 4랑 바꾸면 총 2번만 바꾸면 되니까

size/2 이것이 반복하는 횟수인데 int형이기 때문에 2.5여도 소수점 밑은 없어지고

2만 남게 되겠죠?

그럼 보기 편하게 바꿔보면

for(i=0; i<2; i++){                           이런식으로 써도 무방할거에요.

r=size-1-i;

temp=ary[i];

ary[i]=ary[r];

ary[r]=temp;

}

그럼 반복하는건 i가 0부터 시작하니깐 0과 1, 이렇게 두번 반복하겠네요.

r=size-1-i;   이건 3을 기준으로 오른쪽 값들의 위치를 구하는건데요.

0이들어가면 r의 값은 4가 될것이고 1이들이가면 3이 되겠죠?

그 밑에 temp=ary[i];  여기부터는

a를 i라고 생각하고 b를 r이라 생각하면 저런 방식으로 해서 위치가 바뀌게 되요.

이렇게해서 연습문제까지 풀어봤구요.

다음 포스팅에서는 문자열을 저장하는 문자배열에 대해 살펴볼게요~^^