정수형 요소로 구성된 배열이 주어졌을 때, 중복된 값을 제거하고 고유한(distinct) 요소만 골라 정렬된 순서로 출력하는 것이 이번 글의 목표입니다.
예를 들어 4, 6, 5, 3, 4, 5, 2, 8, 7, 0과 같은 정수 값들이 저장된 배열이 있다고 가정해 보겠습니다. 이 배열을 단순히 오름차순으로 정렬하면 0, 2, 3, 4, 4, 5, 5, 6, 7, 8이 되지만, 여기에는 여전히 중복된 값인 4와 5가 남아 있습니다. 따라서 중복을 제거한 최종 결과는 0, 2, 3, 4, 5, 6, 7, 8이 됩니다.
예제
입력: array[] = {4, 6, 5, 3, 4, 5, 2, 8, 7, 0}
출력: 0 2 3 4 5 6 7 8문제 해결 접근 방법
원하는 결과를 얻기 위해 다음 세 가지 단계를 거칩니다.
- 배열을 처음부터 끝까지 탐색하면서 고유한 요소만 별도의 배열(array1)에 저장합니다.
- 고유한 값만 담긴 array1을 정렬합니다.
- 정렬된 array1의 값을 차례대로 출력합니다.
알고리즘
START
STEP 1: 변수 i, j, array1[size], temp 선언 및 count = 0으로 초기화
STEP 2: i = 0부터 i < size까지 반복
j = i+1부터 j < size까지 반복
IF array[i] == array[j] THEN
break (중복 발견)
END IF
END FOR
IF j == size THEN
array1[count++]에 array[i] 저장
END IF
END FOR
STEP 3: i = 0부터 i < count-1까지 반복 (선택 정렬)
j = i+1부터 j < count까지 반복
IF array1[i] > array1[j] THEN
array1[i]와 array1[j] 교환(SWAP)
END IF
END FOR
END FOR
STEP 4: array1 출력
STOP
C 언어 구현 예제
#include <stdio.h>
/* 배열의 고유한 요소들을 정렬하여 출력하는 함수 */
void printDistinctElements(int array[], int size) {
int i, j, array1[size], temp, count = 0;
/* 1단계: 고유한 요소만 array1에 저장 */
for(i = 0; i < size; i++) {
for(j = i+1; j < size; j++) {
if(array[i] == array[j]) {
/* 중복 요소를 발견하면 내부 반복 종료 */
break;
}
}
/* j가 size와 같다면 배열 전체를 탐색했음에도
array[i]의 중복값을 찾지 못했다는 의미 */
if(j == size) {
array1[count++] = array[i];
}
}
/* 2단계: 고유한 값만 저장된 array1을 선택 정렬 */
for(i = 0; i < count-1; i++) {
for(j = i+1; j < count; j++) {
if(array1[i] > array1[j]) {
temp = array1[i];
array1[i] = array1[j];
array1[j] = temp;
}
}
}
/* 3단계: 정렬된 결과 출력 */
for(i = 0; i < count; ++i) {
printf("%d ", array1[i]);
}
}
int main() {
int array[] = {4, 6, 5, 3, 4, 5, 2, 8, 7, 0};
int n = sizeof(array)/sizeof(array[0]);
printDistinctElements(array, n);
return 0;
}
실행 결과
위 프로그램을 실행하면 다음과 같은 출력이 생성됩니다.
0 2 3 4 5 6 7 8
동작 원리 정리
핵심 아이디어는 간단합니다. 각 요소에 대해 자신보다 뒤에 있는 모든 요소와 비교했을 때 같은 값이 하나도 없다면, 그 요소는 고유한 값입니다. 이런 요소만 새 배열에 모은 뒤, 선택 정렬(selection sort)로 오름차순 정렬하여 출력하면 됩니다.
이 방식의 시간 복잡도는 중복 제거 단계에서 O(n²), 정렬 단계에서 O(k²)(k는 고유 요소의 개수)이므로 전체적으로 O(n²)에 해당합니다. 배열의 크기가 크지 않은 경우에는 충분히 실용적인 접근 방법입니다.