[C] 백준 1059번: 수2

 테스트케이스가 별로 없어서 약간 해멘 문제이다. 실제로 틀리는 사람들 중에는 테이스케이스가 딱 하나 밖에 없어서 헷갈려 틀리는 경우가 대다수일거라고 생각된다.  

입출력 예시

입력	출력
2 1 5 3	3

힌트) Lucky Set이 1, 5이고 N이 3인 경우 N을 포함하는 Unlucky 구간은 [2, 3]. [2, 4], [3, 4]로 3가지이다.

입력	출력
4 1 7 14 10 5	7

힌트) Lucky Set이 1, 7, 14, 10이고 N이 5인 경우 N을 포함하는 Unlucky 구간은 [2, 5], [2, 6], [3, 5], [3, 6], [4, 5], [4, 6], [5, 6]로 7가지이다.

정답 코드

#include <stdio.h>

void sort(int *, int);
int search_Unlucky(int *, int, int);

int main() {

	int Lucky_Set[50];
	int L;

	int N;

	int result;

	int i;

	scanf("%d", &L);

	for (i = 0; i < L; i++) {
		scanf("%d", Lucky_Set + i);
	}

	scanf("%d", &N);

	sort(Lucky_Set, L);

	result = search_Unlucky(Lucky_Set, L, N);

	printf("%d", result);

	return 0;
	
}

void sort(int *arr, int n) {

	int i, j;
	int tmp;

	for (i = 0; i < n - 1; i++) {
		for (j = i + 1; j < n; j++) {
			if (arr[i] > arr[j]) {
				tmp = arr[i];
				arr[i] = arr[j];
				arr[j] = tmp;
			}
		}
	}

}

int search_Unlucky(int *arr, int n, int N) {

	int i, j;

	int least = 1, large;
	int count = 0;

	for (i = 0; i < n; i++) {
		if (N <= arr[i]) {
			large = arr[i];
			break;
		}
		least = arr[i] + 1;
	}

	for (i = least; i < large; i++) {
		for (j = i + 1; j < large; j++) {
			if (i <= N && N <= j) {
				count++;
			}
		}
	}

	return count;

}

코드 설명

 L을 입력 받고, Lucky Set의 정수들을 입력 받는다. Unlucky 구간을 찾을 때 편의성을 위해 배열을 정렬해주고, Unlucky 구간을 탐색한다. Unlucky 구간의 개수를 세는 방법은 다음과 같다.

1. least는 Unlucky 구간이 될 수 있는 최소의 정수, large는 최대의 정수이다. least는 1로 초기화한다. 

2. 첫번째 for문에서는 large와 least를 갱신하는 작업을 한다. N보다 큰 Lucky Set의 정수가 나오면 large를 해당 정수로 교체하고 for문을 빠져나온다. 이 정수 이상의 숫자는 Unlucky 구간에 포함할 수 없기 때문이다. 만약 N보다 작은 정수라면 least를 해당 정수로 교체해준다.

3. 두번째는 2중 for문이다. Unlucky 구간의 개수를 세는 작업을 한다. i는 시작지점, j는 끝지점이다. 즉, 구간 [i, j]가 된다. 구간 [i, j]에 N이 포함되어있는지 검사하고, 포함되어 있으면 count를 1 증가시킨다.

4. count를 반환한다.