[C] 누락된 숫자 찾아내기

www.notion.so/2-b2662d00929d4c24993586636fc2115d

✔︎ 문제 2. 누가 빠졌는지 찾아보자!

1. 미션 제목

누가 빠졌는지 찾아보자!

2. 지시문

1 부터 N 까지의 숫자 모음이 있다. 여기서 K 라는 숫자가 빠진 N – 1 개의 파일이 있다. K 라는 숫자를 찾아보자.

• N 은 2 이상 500,000 이하의 값을 가짐
• 정렬되지 않은 숫자들의 모음 파일이 주어짐 (ex, 10.txt 100.txt 1_000.txt 10_000.txt 100_000.txt, 500_000.txt)
• 위 파일에서 빠진 숫자 K 를 찾아라
• 파일의 값을 읽어 n 과 k 가 빠진 arr 이를 저장하는 참고 코드는 아래 참고 (파일은 제공된 파일 사용)
• 파일 구조: 첫 줄에는 N 값이 주어지고, 그 아래 줄에는 공백으로 K 를 제외한 N – 1 개의 숫자들이 나열 됨

참고 코드

#include <stdio.h>
#define SIZE 500000

int main(int arge, char*argv[]) {
    int n;

    scanf("%d", &n);

    // 1부터 N의 숫자중 K가 빠진 배열
    int partArr[SIZE];
    int lengthOfPartArr = n-1;

    for(int i=0; i < lengthOfPartArr; i++){
        scanf("%d", &partArr[i]);
    }

    // TODO: n과 partArr를 이용하여, K를 구하라
    return 0;
}

정렬되지 않은 숫자들의 모음 파일

미션03_텍스트파일.zip

 

Figure 1 - 실행 예시 및 정답

10.txt: k = 7

100.txt: k = 57

1_000.txt: k = 507

10_000.txt: k = 8072

100_000.txt: k = 96676

500_000.txt: k = 264936

 

3. 핵심 개념#배열 #정수합 #합의공식 #반복문

 

4. 부가 설명- 표준입출력: https://www.tutorialspoint.com/cprogramming/c_input_output.htm- redirection 을 이용한 파일입력: https://www.cs.bu.edu/teaching/c/file-io/intro/- https://en.wikipedia.org/wiki/1_%2B_2_%2B_3_%2B_4_%2B_⋯

 

나의 풀이

#include<stdio.h>
#include<stdlib.h>
#include<time.h>

#define SIZE 500000

int* charArrayToIntArray(char *target[], const int length);
int findLossNum(int count, int array[]);
void quickSort(int* data, int start, int end);
int duplicatedNum(int sortedArr[], int length);

int main(int argc, char* argv[]) {
    // 시간 측정 [START]
    clock_t begin = clock();
    int n;

    scanf("%d", &n);

    // 1부터 N의 숫자 중 K가 빠진 배열
    int partArr[SIZE];
    int lengthOfPartArr = n - 1;

    for(int i = 0 ; i < lengthOfPartArr; i++) {
        scanf("%d", &partArr[i]);
    }

    // Sorting
    quickSort(partArr, 0, lengthOfPartArr - 1);

    // 인자 검사
    int maxNum = partArr[lengthOfPartArr-1];
    if(maxNum > n) {
        printf("입력 범위를 벗어난 입력이 있습니다.\n");
				printf("프로그램을 종료합니다.\n");
        return 1;
    }

    // 중복 검사
    int checkDuplicate = duplicatedNum(partArr, lengthOfPartArr);
    if(checkDuplicate != 0) {
        printf("\n중복된 숫자가 입력되었습니다 : %d\n", checkDuplicate);
        printf("프로그램을 종료합니다.\n");
        return 1;
    }

    // TODO: n과 partArr를 이용하여, K를 구하라
    int foundNum = findLossNum(lengthOfPartArr, partArr);
    if(foundNum >= 1 && foundNum <= n) {
        printf("누락된 숫자(K) : %d\n", foundNum);

        clock_t end = clock();
        double time_spend = (double)(end - begin) / CLOCKS_PER_SEC;
        printf("\n\n[ 프로그램 수행 시간 : %.3f초 ]\n", time_spend);
    }
    else {
        printf("검출 오류! 입력된 값을 확인하세요.\n");
        return 1;
    }
}

int* charArrayToIntArray(char *target[], const int length) {
	int *result = malloc(sizeof(int) * length);

	for (int i = 0; i < length; i++) {
		result[i] = atoi(target[i + 1]);
	}

	return result;
}

int findLossNum(int length, int array[]) {
    // myArray를 length + 1 크기로 설정하고 0으로 초기화
    int* myArray = calloc(length + 1, sizeof(int));

    // 입력된 숫자에 Flag를 세움
    for(int i = 0 ; i < length ; i++) {
        myArray[array[i] - 1] = 1;
    }

    // myArray를 순회하며 Flag가 세워지지 않은 숫자 검출
    for(int i = 0 ; i < length + 1; i++) {
        if(myArray[i] == 0) {
            return i + 1;
        }
    }

    // 검출되지 않으면 -1 리턴
    return -1;
}

void quickSort(int* data, int start, int end) {
    // 원소가 1개
    if(start >= end) {
        return;
    }

    int pivot = start;
    int i = pivot + 1;
    int j = end;
    int temp;

    while(i <= j) {
        while(i <= end && data[i] <= data[pivot]) {
            i++;
        }
        while(j > start && data[j] >= data[pivot]) {
            j--;
        }

        if(i > j) {
            temp = data[j];
            data[j] = data[pivot];
            data[pivot] = temp;
        } else {
            temp = data[i];
            data[i] = data[j];
            data[j] = temp;
        }
    }

    quickSort(data, start, j - 1);
    quickSort(data, j + 1, end);
}

int duplicatedNum(int sortedArr[], int length) {
    int num = 0;
    for(int i = 0; i < length - 1; i++) {
        if(sortedArr[i] == sortedArr[i+1]) {
            num = sortedArr[i];
        }
    }
    return num;
}

구현한 기능

• 리다이렉션으로 배열에 파일에 기록된 숫자 입력
• 배열에 저장된 숫자들을 정렬함 (Quick 정렬 알고리즘 사용)
• 중복 검사를 하여 중복된 숫자가 입력된 경우 프로그램을 종료함
• 위 과정에서 프로그램이 예외 없이 동작한 경우 범위 내에서 누락된 값을 찾음 (calloc과 Flag 사용)
  • 이 과정에서 오류가 있을 경우 사용자에게 알리고 프로그램 종료
• 프로그램 정상 종료 후 프로그램이 동작한 시간 표시함

정상적으로 진행된 프로그램

정상적인 프로그램 진행

범위를 벗어난 입력이 있는 경우

첫 번째 숫자를 N(100000)보다 큰 숫자로 변경

 

중복된 숫자가 입력된 경우

첫 번째 숫자와 두 번째 숫자를 같게 설정

중복된 숫자를 찾아주고 프로그램 종료

---

나의 풀이 (미션 수정 이전)

#include<stdio.h>
#include<stdlib.h>

#define SIZE 500000

int* charArrayToIntArray(char *target[], const int length);
int findLossNum(int count, int array[]);
void quickSort(int* data, int start, int end);
int duplicatedNum(int sortedArr[], int length);

int main(int argc, char* argv[]) {
    int n;
    // 1부터 N의 숫자 중 K가 빠진 배열
    int partArr[SIZE];
    int lengthOfPartArr;

    if (argc < 2) {
        printf("몇 개의 숫자를 입력할 것인가요?\n");
        do {
            printf("2 이상, 500,000 이하의 값 : ");
            scanf("%d", &n);
        } while(n < 2 || n > SIZE);
        printf("\n");

        lengthOfPartArr = n - 1;

        for(int i = 0 ; i < lengthOfPartArr ; i++) {
            printf("[%d/%d]1~%d까지의 수 중 하나 입력(중복X) : ", i + 1, n - 1, n);
            scanf("%d", &partArr[i]);

            // 입력 범위 검사
            if(partArr[i] > n || partArr[i] < 1) {
                i--;
                printf("입력 범위를 벗어났습니다.\n\n");
            }
        }
    }
    else {
        n = argc;
        lengthOfPartArr = n - 1;
        int* terminalInputNum = charArrayToIntArray(argv, argc - 1);
        for(int i = 0 ; i < lengthOfPartArr; i++) {
            partArr[i] = terminalInputNum[i];
        }
    }

    // Sorting
    quickSort(partArr, 0, lengthOfPartArr - 1);

    // 콘솔에서 입력된 인자의 수 검사
    int maxNum = partArr[lengthOfPartArr-1];
    if(maxNum > n) {
        printf("인수가 부족합니다.\n");
        return 1;
    }

    printf("\n*** 입력된 숫자 목록 (1~%d) ***\n", n);
    for(int i = 0 ; i < lengthOfPartArr; i++) {
        printf("%d  ", partArr[i]);
    }
    printf("\n\n");

    // 중복 검사
    int checkDuplicate = duplicatedNum(partArr, lengthOfPartArr);
    if(checkDuplicate != 0) {
        printf("\n중복된 숫자가 입력되었습니다 : %d\n", checkDuplicate);
        printf("프로그램을 종료합니다.\n");
        return 1;
    }

    // TODO: n과 partArr를 이용하여, K를 구하라
    int foundNum = findLossNum(lengthOfPartArr, partArr);
    if(foundNum >= 1 && foundNum <= n) {
        printf("누락된 숫자 : %d\n", foundNum);
    }
    else {
        printf("검출 오류! 입력된 값을 확인하세요.\n");
        return 1;
    }
}

int* charArrayToIntArray(char *target[], const int length) {
	int *result = malloc(sizeof(int) * length);

	for (int i = 0; i < length; i++) {
		result[i] = atoi(target[i + 1]);
	}

	return result;
}

int findLossNum(int length, int array[]) {
    // myArray를 length + 1 크기로 설정하고 0으로 초기화
    int* myArray = calloc(length + 1, sizeof(int));

    // 입력된 숫자에 Flag를 세움
    for(int i = 0 ; i < length ; i++) {
        myArray[array[i] - 1] = 1;
    }

    // myArray를 순회하며 Flag가 세워지지 않은 숫자 검출
    for(int i = 0 ; i < length + 1; i++) {
        if(myArray[i] == 0) {
            return i + 1;
        }
    }

    // 검출되지 않으면 -1 리턴
    return -1;
}

void quickSort(int* data, int start, int end) {
    // 원소가 1개
    if(start >= end) {
        return;
    }

    int pivot = start;
    int i = pivot + 1;
    int j = end;
    int temp;

    while(i <= j) {
        while(i <= end && data[i] <= data[pivot]) {
            i++;
        }
        while(j > start && data[j] >= data[pivot]) {
            j--;
        }

        if(i > j) {
            temp = data[j];
            data[j] = data[pivot];
            data[pivot] = temp;
        } else {
            temp = data[i];
            data[i] = data[j];
            data[j] = temp;
        }
    }

    quickSort(data, start, j - 1);
    quickSort(data, j + 1, end);
}

int duplicatedNum(int sortedArr[], int length) {
    int num = 0;
    for(int i = 0; i < length - 1; i++) {
        if(sortedArr[i] == sortedArr[i+1]) {
            num = sortedArr[i];
        }
    }
    return num;
}

구현한 기능

./mission3_2_upgrade 2 6 5 3 1 .. 와 같이 콘솔에서 인자로 숫자들을 입력하여 실행한 경우

• 콘솔에서 입력 받은 숫자들을 문자형→숫자형 으로 변환하여 배열에 저장
• 배열에 저장된 숫자들을 정렬함 (퀵 정렬 알고리즘 사용)
• 콘솔에서 입력 받은 숫자들의 개수가 부족하다면 사용자에게 알리고 프로그램 종료
• 정렬된 숫자 목록을 출력하여 보여줌
• 중복 검사를 하여 중복된 숫자가 입력된 경우 프로그램을 종료함
• 위 과정에서 프로그램이 예외 없이 동작한 경우 범위 내에서 누락된 값을 찾음 (calloc과 Flag 사용)
  • 이 과정에서 오류가 있을 경우 사용자에게 알리고 프로그램 종료

./mission3_2_upgrade 로 인자 없이 프로그램만 실행한 경우

• 입력 받을 숫자 범위 지정 기능
  • 입력 받은 범위가 2 보다 작거나 SIZE(500,000) 보다 클 경우 다시 입력 받는 기능
• 입력 받은 범위 - 1 만큼 숫자를 입력 받음
  • 입력 범위를 벗어난 경우 사용자에게 알리고 다시 입력을 받도록 함
• 입력 받은 숫자들을 정렬함 (퀵 정렬 알고리즘 사용)
• 정렬된 숫자 목록을 출력하여 보여줌
• 중복 검사를 하여 중복된 숫자가 입력된 경우 프로그램을 종료함
• 위 과정에서 프로그램이 예외 없이 동작한 경우 범위 내에서 누락된 값을 찾음 (calloc과 Flag 사용)
  • 이 과정에서 오류가 있을 경우 사용자에게 알리고 프로그램 종료

실행 결과

./mission3_2_upgrade 2 6 5 3 1 .. 와 같이 콘솔에서 인자로 숫자들을 입력하여 실행한 경우

인자가 부족한 경우 + 정상 동작한 경우

./mission3_2_upgrade 로 인자 없이 프로그램만 실행한 경우

중복 입력된 경우

입력 범위를 벗어난 경우 + 정상적으로 동작한 경우

---

이전소스코드(main 입력 사용 x)

#include<stdio.h>
#include<stdlib.h>

#define SIZE 500000

int findLossNum(int count, int array[]);
void quickSort(int* data, int start, int end);
int duplicatedNum(int sortedArr[], int length);

int main(void) {
    int n;

    printf("몇 개의 숫자를 입력할 것인가요?\n");
    do {
        printf("2 이상, 500,000 이하의 값 : ");
        scanf("%d", &n);
    } while(n < 2 || n > SIZE);
    printf("\n");

    // 1부터 N의 숫자 중 K가 빠진 배열
    int partArr[SIZE];
    int lengthOfPartArr = n - 1;

    for(int i = 0 ; i < lengthOfPartArr ; i++) {
        printf("[%d/%d]1~%d까지의 수 중 하나 입력(중복X) : ", i + 1, n - 1, n);
        scanf("%d", &partArr[i]);

        // 입력 범위 검사
        if(partArr[i] > n || partArr[i] < 1) {
            i--;
            printf("입력 범위를 벗어났습니다.\n\n");
        }
    }

    // Sorting
    quickSort(partArr, 0, lengthOfPartArr - 1);

    printf("\n*** 입력된 숫자 목록 (1~%d)***\n", n);
    for(int i = 0 ; i < lengthOfPartArr; i++) {
        printf("%d  ", partArr[i]);
    }
    printf("\n\n");

    // 중복 검사
    int checkDuplicate = duplicatedNum(partArr, lengthOfPartArr);
    if(checkDuplicate != 0) {
        printf("\n중복된 숫자가 입력되었습니다 : %d\n", checkDuplicate);
        printf("프로그램을 종료합니다.\n");
        return 1;
    }

    // TODO: n과 partArr를 이용하여, K를 구하라
    int foundNum = findLossNum(lengthOfPartArr, partArr);
    if(foundNum >= 1 && foundNum <= n) {
        printf("누락된 숫자 : %d\n", foundNum);
    }
    else {
        printf("검출 오류! 입력된 값을 확인하세요.\n");
        return 1;
    }
}

int findLossNum(int length, int array[]) {
    // myArray를 length + 1 크기로 설정하고 0으로 초기화
    int* myArray = calloc(length + 1, sizeof(int));

    // 입력된 숫자에 Flag를 세움
    for(int i = 0 ; i < length ; i++) {
        myArray[array[i] - 1] = 1;
    }

    // myArray를 순회하며 Flag가 세워지지 않은 숫자 검출
    for(int i = 0 ; i < length + 1; i++) {
        if(myArray[i] == 0) {
            return i + 1;
        }
    }

    // 검출되지 않으면 -1 리턴
    return -1;
}

void quickSort(int* data, int start, int end) {
    // 원소가 1개
    if(start >= end) {
        return;
    }

    int pivot = start;
    int i = pivot + 1;
    int j = end;
    int temp;

    while(i <= j) {
        while(i <= end && data[i] <= data[pivot]) {
            i++;
        }
        while(j > start && data[j] >= data[pivot]) {
            j--;
        }

        if(i > j) {
            temp = data[j];
            data[j] = data[pivot];
            data[pivot] = temp;
        } else {
            temp = data[i];
            data[i] = data[j];
            data[j] = temp;
        }
    }

    quickSort(data, start, j - 1);
    quickSort(data, j + 1, end);
}

int duplicatedNum(int sortedArr[], int length) {
    int num = 0;
    for(int i = 0; i < length - 1; i++) {
        if(sortedArr[i] == sortedArr[i+1]) {
            num = sortedArr[i];
        }
    }
    return num;
}