[백준 - C#] 1059번 좋은 구간

문제링크

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

1059번: 좋은 구간

 

문제

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

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

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

조건

시간제한 : 2초
메모리 제한 : 128 MB

입력

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

출력

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

 

문제정리

1. n을 포함하는 [A, B] 구간을 구하자
2. n은 집합 S에 속하지 않는다.
3. n은 집합 S의 최소 값보다 작을 수 있다.

이번 문제의 경우 브루트포스 알고리즘으로 집합 S에서 n의 위치를 찾고 모든 구간을 구하는 방식으로 문제풀이를 진행하였습니다.

처음에 S 값을 오름차순으로 정렬하기전에 0값을 넣어준 이유는 n의 값이 S[0]값보다 작을 수 있기 때문입니다.

반례 : 3 / 7 8 9 / 2

n의 값은 2인데 S[0]값은 7로 n이 작기 때문에 1~6까지 n을 포함하는 구간을 다 구할 수 있게 되기 때문입니다.

 

S의 모든 구간을 반복문으로 돌리며 n의 위치를 찾게 되면 그때부터 n을 포함하는 모든 구간을 구하게 됩니다.

모든 구간을 구하는 방식은 초기 A값과 B값을 하나씩 증가시키며 모든 구간을 확인하다 해당하는 조건이 충족되면 구간을 카운팅하는 방식으로 문제풀이를 진행하였습니다.

 

C# 코드

static void Main(string[] args)
{
    StreamWriter writer = new StreamWriter(OpenStandardOutput());
    StreamReader reader = new StreamReader(OpenStandardInput());
 
    int L = int.Parse(reader.ReadLine());
    List<int> input = Array.ConvertAll(reader.ReadLine().Split(), int.Parse).ToList();
    int n = int.Parse(reader.ReadLine());
    input.Add(0); // n의 값이 S[0]의 값보다 작은 경우를 확인하기 위해 S[0] = 0값을 추가
    int[] S = input.ToArray();
    Array.Sort(S);
 
    int count = 0;
    int index = 1;
    int min = 0;
 
    for (int i = 0; i < S.Length; i++)
    {
        if (S[i] < n && n < S[i + 1]) // 정수 집합 S에서 n의 위치를 찾기 위한 조건
        {
            min = S[i] + 1; // 초기 A 값
            while (true)
            {
                if (min + index >= S[i + 1]) // B 값이 집합 S의 값에 도달한다면 초기화
                {
                    index = 1;
                    min++;
                }
 
                if (min >= S[i + 1] || min + index >= S[i + 1]) // 구간 A와 B 의 값이 좋은 구간을 벗어난다면 종료
                    break;
 
                if (min <= n && n <= min + index) // 좋은 구간 카운팅
                    count++;
 
                index++;
            }
 
            break;
        }
    }
 
    writer.WriteLine(count);
 
    writer.Close();
    reader.Close();
}

읽어주셔서 감사합니다 오늘도 즐거운 하루 되세요.