[C언어] 백준 1059 좋은 구간

문제

정수 집합 S가 주어졌을때, 다음 조건을 만족하는 구간 [A, B]를 좋은 구간이라고 한다.

• A와 B는 양의 정수이고, A < B를 만족한다.
• A ≤ x ≤ B를 만족하는 모든 정수 x가 집합 S에 속하지 않는다.

집합 S와 n이 주어졌을 때, n을 포함하는 좋은 구간의 개수를 구해보자.

입력

첫째 줄에 집합 S의 크기 L이 주어진다. 둘째 줄에는 집합에 포함된 정수가 주어진다. 셋째 줄에는 n이 주어진다.

출력

첫째 줄에 n을 포함하는 좋은 구간의 개수를 출력한다.

제한

• 1 ≤ L ≤ 50
• 집합 S에는 중복되는 정수가 없다.
• 집합 S에 포함된 모든 정수는 1보다 크거나 같고, 1,000보다 작거나 같다.
• 1 ≤ n ≤ (집합 S에서 가장 큰 정수)

https://www.acmicpc.net/problem/1059

1059번: 좋은 구간

 

문제 이해하는데 좀 오래걸리는 문제 인것 같네요

입력받은 n이 배열 어느 이어진 두 수의 초과와 미만을 만족할 때를 좋은 구간 이라고 합니다.

저는 이걸 이해하는데 조금 오래 걸렸습니다.

입력받은 n이 배열의 첫 번째 요소보다 작을 시 배열[0]번째 전에 0이 있다고 가정하고 풀어야 하는것도 잊으시면 안됩니다.

 

그럼 이제 문제를 어느정도 이해 했으니 문제가 요구하는것을 해석해야 합니다.

 

"A와 B는 양의 정수이고, A < B를 만족한다." 라는 내용을 보면 오름차순 정렬을 해야한다는 내용을 암시합니다.

즉 저희는 입력받은 난수 배열을 정렬시키는게 step 1 이라고 보시면 될것 같습니다.

 

void	sort(int nums[t])
{
	for(int i = 0; i < t; i++)
	{
		int	m = 2147483647;
		int k;
		for(int j = i; j < t; j++)
		{
			if (m > nums[j])
			{
				m = nums[j];
				k = j;
			}
		}
		swap(nums[k], nums[i]);
	}
}

저는 정렬 알고리즘으로 선택 정렬을 사용했습니다.

굳이 선택 정렬을 쓴 이유는 구현하기 제일 쉬워서(?)입니다.

 

void	count(int n1, int n2)
{
	for (int i = n1; i <= n; i++)
	{
		if (i > n)
			break ;
		for (int j = n; j < n2; j++)
		{
			if (i == j)
				continue ;
			result++;
		}
	}
}

좋은 구간을 찾아 줄 count함수 입니다.

i를 n1로 입력받아 i가 n보다 이하일 때까지 반복하고

j를 n으로 입력받아 n2 전까지 반복하면서 카운트를 하면 됩니다.

"집합 S에는 중복되는 정수가 없다."

이 조건을 i와 j가 같을 때로 따로 조건을 걸어서 pass하게끔 설정을 해줍니다.

 

int main(void)
{
    scanf("%d", &t);
    int nums[t];

    for(int i = 0; i < t; i++)
        scanf("%d", &nums[i]);
    scanf("%d", &n);
    sort(nums);
    if (n < nums[0])
    	count(1, nums[0]);
    else
    {
       	for(int i = 0; i < t - 1; i++)
        {
            if (nums[i] < n && nums[i + 1] > n)
                 count(nums[i] + 1, nums[i + 1]);
        }
    }
    printf("%d\n", result);
    return (0);
}

main 함수입니다.

맨 처음 배열을 정렬 시켜 줍니다.

이후 맨 처음 설명 드렸듯 입력받은 n이 배열의 첫 번째 요소보다 작을 때

배열[0]번째 전에 0이 있다고 가정하고 풀어야 하는것도 잊으면 안된다고 했죠?

그래서 count함수에 n1을 1로, n2를 nums[0]으로 설정하고

 

배열[0]번째 보다 큰 경우 따로 for문으로 반복 실행하는데

현재 요소가 n미만 이면서 다음 요소가 n초과인 경우 count 해줍니다

현재 요소보다 1크게 n1을 설정하고, 다음 요소를 n2로 설정해서 좋은 구간을 탐색해줍니다.

 

탐색을 다 한뒤 출력을 하면서 프로그램이 종료되게 설정하면 끝입니다.

 

 

반응형

전체 코드

#include <stdio.h>
#define swap(a, b) {int t = a; a = b; b = t;}
int n, t, result = 0;

void	count(int n1, int n2)
{
	for (int i = n1; i <= n; i++)
	{
		if (i > n)
			break ;
		for (int j = n; j < n2; j++)
		{
			if (i == j)
				continue ;
			result++;
		}
	}
}

void	sort(int nums[t])
{
	for(int i = 0; i < t; i++)
	{
		int	m = 2147483647;
		int k;
		for(int j = i; j < t; j++)
		{
			if (m > nums[j])
			{
				m = nums[j];
				k = j;
			}
		}
		swap(nums[k], nums[i]);
	}
}

int main(void)
{
    scanf("%d", &t);
    int nums[t];

    for(int i = 0; i < t; i++)
        scanf("%d", &nums[i]);
    scanf("%d", &n);
	sort(nums);
	if (n < nums[0])
		count(1, nums[0]);
	else
	{
    	for(int i = 0; i < t - 1; i++)
	    {
			if (nums[i] < n && nums[i + 1] > n)
				count(nums[i] + 1, nums[i + 1]);
		}
    }
    printf("%d\n", result);
    return (0);
}