[부스트 코딩 뉴비 챌린지 2020] week3_미션02

✔︎ 문제 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 50000

int main(int argc, char *argv[]) {
	int n;
    
    scanf("%d", &n);	//ex) ./mission03 < 10.txt의 10이 입력됨
    
    //1부터 N의 숫자 중 k가 빠진 배열
    int partArr[SIZE];
    int lengthOfPartArr = n - 1;
    
    for(int i = 0; i < lengthOfPartArr; i++){	//partArray에 값을 모두 기입
    	scanf("%d", &partArr[i]);
    }
    
    //TODO: n과 partArr를 이용하여 K를 구하라
    return 0;
}

 

정렬되지 않은 숫자들의 모음 파일 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_%E2%8B%AF

 

 

문제 풀이

방법1) N-1개의 값을 받고 오름차순 정렬하여 중간에 빠진 값을 비교해가면서 찾는다.

방법2) 합의 공식을 이용한다. ✔︎

 

1부터 N까지 합을 구하고 K가 빠진 N-1개의 숫자의 합을 구해서 그 차이를 구하면 K가 나온다.

전체합 - 입력받은 수의 합 = k

 

#include <stdio.h>

#define SIZE 50000

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

    //파일에서 첫 번째 N을 입력
    scanf("%d", &n);

    //1부터 N까지 숫자 중 K가 빠진 배열을 선언함
    int part_arr[SIZE];
    int length_of_part_arr = n-1;

    //파일에서 N-1개의 숫자를 입력
    for (int i = 0; i < length_of_part_arr; i++)
        scanf("%d", &part_arr[i]);

    int part_sum = 0;


    //N - 1 개의 숫자의 합을 구함
    for (int i = 0; i < length_of_part_arr; i++)
        part_sum += part_arr[i];

    //N개의 합을 구함
    int total_sum = n * (n+1) /2;

    //합의 차로 빠진 수인 k를 구함
    int k = total_sum - part_sum;

    printf("K = %d\n", k);

    return 0;
}