백준 5597번 배열의 차집합 활용

여러가지 풀이법이 있을 수 있겠지만 

우선적으로 생각한것이 1~30의 값을 모두 가지는 배열을 하나 정의하고

입력받은 28개의 숫자들을 가진 배열을 하나 정의해서

두 배열의 차집합을 구하면 문제를 해결할 수 있을거라 생각하여

다음과 같이 배열의 차집합을 구하는 코드를 만들어보았다.

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int main() {
   
  
    int A[28];
    int B[30];
   
    int found;
    
    for (int i = 0; i < 30; i++) {
        B[i] = i+1;
        //1~30을 모두 가지는 배열 정의
    }
    
    for (int i = 0; i < 28; i++) {
        scanf("%d", &A[i]);
        //입렵받은 수로 배열 만들기
    }

    int C[30] = { 0 };
    //차집합 배열 초기화
    for (int i = 0; i < 30; i++) {	//배열원소 하나씩 다른배열에 있는지 비교
        found = 0;	//
        for (int j = 0; j < 28; j++) {
            if (B[i] == A[j]) {
                found = 1;	//발견하면 제외
                break;
            }
        }
        if (found==0) {	//미발견된 수를 차집합 배열에 추가
            C[i] = B[i];
        }
    }


    for (int i = 0; i < 30; i++) {
        if (C[i] != 0) {
            printf("%d\n",C[i]);
        }
        
    }
    return 0;
}

배열의 차집합을 구하는 알고리즘에 대하여 설명하자면

• 첫 번째 배열(1~30을 모두 가지는 배열, B[30] ) 의 각 요소를 두 번째 배열(28개의 숫자를 가지는 배열 A[28] )의 모든 요소와 비교한다.
• 첫 번째 배열의 요소가 두 번째 배열에 없는 경우, 그 요소를 차집합 배열(배열 C[30] )에 추가한다.
• 이를 모든 요소에 대해 반복(30번 반복)하여 최종 차집합 배열을 만든다.

후에 교집합과 합집합에 대해서도 정리할 예정이다.

---

배열의 차집합 대신 답만 간결하게 구하려면 다음과 같은 코드를 써도 된다.

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

main() {
	int a[30] = { 0 }, i, t;

	for (i = 0; i < 28; i++) {
		scanf("%d", &t);
		a[t - 1] = 1;
	}
	for (i = 0; i < 30; i++)
		if (a[i] == 0)
			printf("%d\n", i + 1);
}

모든 배열 원소를 0으로 우선 초기화 해두고

입력받은 숫자들만 체크해서 그 인덱스를 기준으로 원소를 1로 설정한다.

그후 1로 초기화 되지않고 0으로 남아있는 원소의 인덱스 값을 출력하면 된다. 

마치 출석부에 1~30까지 있는 수에서 출석한 번호들만 하나씩 1로 바꿔주는 것과 같다. 결석자들은 0으로 남는다.