1.5.7 인덱스 배열
문제 1-7 크기 n인 배열이 주어집니다. 배열을 정렬해 0부터 n-1까지의 모든 값은 배열에 존재하며, 존재하지 않는 값은 -1로 채웁니다. 값 i가 arr[i]에 저장되도록 배열의 값을 정렬해 보세요.
예시
입력 [ 8, -1, 6, 1, 9, 3, 2, 7, 4, -1]
출력 [-1, 1, 2, 3, 4, -1, 6, 7, 8, 9]
첫 번째 해결책 각 인덱스의 원소를 선택해 그 원소의 값에 해당하는 인덱스로 원소를 옮깁니다. 이때 옮기려는 위치에 원래 있던 값으로 이 과정을 반복합니다.8
해결책 1-7-1
void indexArray(int arr[], int size) { for (int i = 0; i < size; i++) { int curr = i; int value = -1; /* 각 원소를 적절한 위치로 옮기기 */ while (arr[curr] != -1 && arr[curr] != curr) { int temp = arr[curr]; arr[curr] = value; value = curr = temp; } /* 위치가 바뀌었는지 확인하기 */ if (value != -1) { arr[curr] = value; } } }
분석
• 이차 시간 복잡도처럼 보이지만, 내부 반복문은 단 하나의 원소만 순회합니다.
• 내부 반복문에서 원소 하나를 처리하면 이 원소는 해당 인덱스 값 또는 -1을 가집니다.
• 시간 복잡도는 O(n)입니다.
8 역주 이 반복은 옮기려는 위치의 값이 -1일 때 멈추고 for 문의 다음 원소로 넘어갑니다