[C언어] 정수 배열 및 문자열에서 중복 원소 찾기, 중복 제거 방법

C언어 배열 중복 탐색 및 제거 예제

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 "로 등장한 적이 있는 원소들만 모아서 배열에 저장된 것을

확인할 수 있습니다.