📙[Algo] 24.01.09 알고리즘

1059번: 좋은 구간

문제 요약
정수 집합 S에서 다음 조건 만족하는 구간 [A,B]를 좋은 구간
   1. A와 B는 양의 정수 && A<B
   2. A≤x≤B를 만족하는 모든 정수 x는 S에 속하지 X
집합 S와 n이 주어질 때 n을 포함하는 좋은 구간 개수?

시간 제한
2초

입력
집합 S의 크기 L (1 ≤ L ≤ 50)
집합에 포함된 정수 (11,000)
n (1~집합 S에서 가장 큰 정수)

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

 

접근법

• A, B에 올 수 있는 애들있으면 각각 카운
  • A : n → n-1 → n-2 …
  • B : n → n+1 → n+2 …
  • 둘 다 이미 집합에 존재한 숫자 만나면 탐색 멈춤
    • 미리 방문 체크를 통해 존재 여부 체크
• A*B-1출력

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int L = Integer.parseInt(br.readLine());

        boolean[] isSetNum = new boolean[12000];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=0; i<L; i++){
            isSetNum[Integer.parseInt(st.nextToken())] = true;
        }

        int n = Integer.parseInt(br.readLine());

        int A=0, B=0;

        int tmp = n;
        while (tmp > 0) {
            if(isSetNum[tmp]) break;
            A++;
            tmp--;
        }

        tmp = n;
        while (tmp < 12000){
            if(isSetNum[tmp]) break;
            B++;
            tmp++;
        }

        if(A==0) System.out.println(0);
        else System.out.println(A*B-1);

    }
}