[1059] 좋은 구간

문제:

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

1059번: 좋은 구간

코드:

import java.util.*;

public class Main {
    public static void main(String[] args) {
        
    	Scanner sc = new Scanner(System.in);
        int L = sc.nextInt(); // 집합의 크기
        int [] arr = new int[1001]; // 지점 저장
        for(int i=0;i<L;i++) { // 지점 입력
        	int A = sc.nextInt();
        	arr[A]++;
        }
        int n = sc.nextInt(); // 주어진 수
        int p1 = 0; // n보다 작으면서 처음으로 만나는 지점
        int p2 = 0; // n보다 크면서 처음으로 만나는 지점

        for(int i=n;i>0;i--) {
        	if(arr[i] == 1) {
        		p1 = i;
        		break;
        	}
        }
        for(int i=n;i<1001;i++) {
        	if(arr[i] == 1) {
        		p2 = i;
        		break;
        	}
        }

        int sum = 0; // 좋은 구간 개수
        
        if((n-1) != p1) {
        	sum += (n-p1-1)*(p2-n);
        }
        sum += p2-n-1;
        
        if(p1 == n || p2 == n) {
        	System.out.println(0); // 구간과 n이 겹치는 경우
        }else {
        	System.out.println(sum);
        }
    }
}

 

 

Scanner sc = new Scanner(System.in);
1.        int L = sc.nextInt(); // 집합의 크기
2.        int [] arr = new int[1001]; // 지점 저장
3.        for(int i=0;i<L;i++) { // 지점 입력
        	int A = sc.nextInt();
        	arr[A]++;
        }
        int n = sc.nextInt(); // 주어진 수

1. L = 집합 S의 크기 

2. 집합 S에 포함된 모든 정수는 1보다 크고 1000보다 작으므로

집합의 포함된 정수를 입력 받을 때 (예제 입력 2번 째 줄) 예외를 발생 시키게 하지 않기 위해 지점 저장을 위한

배열인 arr의 크기를 1001로 설정한다.

3. 각각 지점을 입력받아 (예제 입력 2번 째 줄) 각 지점의 배열 값을 1씩 증가 시킨다.

  만약 1  3  5를 입력 받았을 경우 배열의 모양은

  {0, 1, 0, 0, 1, 0, 0, 1, 0 ...} 이 된다. 

 

 

좋은 구간의 개수는 어떻게 구해야만 할까?

 

예제 입력1을 예로 들어보자.

  위 과정을 수행할 경우 배열의 모양은

  {0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1,  0, 0, 0, 1(14번째),  0, 0, ... }  이다.

  이때 주어진 n = 2 이다.

  그러므로 좋은 구간의 경우 [2,3] ... [2,6] 이다.

 

예제 입력2을 예로 들어보자.

  위 과정을 수행할 경우 배열의 모양은

  {0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0,  0, 0, 1(13번째), 0,  0, 0, ... }    // 13번째 뒤로는 필요 없기에 생략  

  이때 주어진 n=10 이다.

  그러므로 좋은 구간의 경우  [9,10]...[9,12]   &  [10,11],[10,12]가 된다.

 

위 과정을 통해 좋은 구간을 알아내는 식을 구현할 수 있다

1. 	int p1 = 0; // n보다 작으면서 처음으로 만나는 지점
2.      int p2 = 0; // n보다 크면서 처음으로 만나는 지점

        for(int i=n;i>0;i--) {
        	if(arr[i] == 1) {
        		p1 = i;
        		break;
        	}
        }
        for(int i=n;i<1001;i++) {
        	if(arr[i] == 1) {
        		p2 = i;
        		break;
        	}
        }

p1을 n보다 작으면서 처음으로 만나는 지점, p2를 n보다 크면서 처음으로 만나는 지점이라고 하자.

아래 for문은 p1,p2를 알아내기 위한 반복문이다.

 

#1. 만약 n과 p1 사이에 수가 존재하지 않는 경우 (예제 입력 1)

좋은 구간의 수는 [n,n+1] ~ [n,p2-1]    즉, ( p2-n+1 ) 개가 존재한다.  (직접 세어보면 알 수 있다.)

예제 입력 1의 경우  n=2, p2= 7이므로  [2,3] ~ [2,6]  즉, 7-2+1 = 6개

 

#2. 만약 n과 p1 사이에 수가 존재하는 경우 ( 예제 입력 2 )의 경우는 어떻게 될까?

n과 p1 사이에 존재하는 수를 Ki( i = 1,...... ) 라고 하자.

 

좋은 구간의 수는  [k1,n] ~ [k1,p2-1] .... [Kn바로 전 , n] ~ [kn바로 전, p2-1] 개와 [n,n+1] ~ [n,p2-1] 개의 합 만큼 존재한다.

예제 입력 2를 예를 들어보면  K1 = 9 이므로 [9,10] ~ [9,12] , [10,11] ~ [10,12] 만큼 존재한다.

 [k1,n] ~ [k1,p2-1] .... [Kn바로 전 , n] ~ [kn바로 전, p2-1] 를 식으로 바꿔 보면

( n-p1-1 ) * ( p2-n ) 개 ( n과 p1 사이 존재하는 수 개수) * ( n이상 p2 미만 개수 ) 로 바꿔 볼 수 있다.

 

n과 p1 사이 존재하는 수의 경우 항상 범위를 [Ki , n~(p2-1) ]  ( n이상 p2 미만 개수 ) 으로 갖는다.

이것을 식으로 표현한 것.

 

따라서 ( n-p1-1 ) * ( p2-n ) + ( p2-n+1 ) 개가 존재한다.

        int sum = 0; // 좋은 구간 개수
        
        if((n-1) != p1) {
        	sum += (n-p1-1)*(p2-n);
        }
        sum += p2-n-1;
        
        if(p1 == n || p2 == n) {
        	System.out.println(0); // 구간과 n이 겹치는 경우
        }else {
        	System.out.println(sum);
        }

#1의 경우 ( n과 p1 사이에 값이 존재하지 않는 경우 ) 는 ( n-p1-1 ) * ( p2-n ) 를 수행할 이유가 없고

#2의 경우 ( n-p1-1 ) * ( p2-n ) 를 수행해야 한다.

	if((n-1) != p1) {
        	sum += (n-p1-1)*(p2-n);
        }

if문을 통해 경우를 따져 ( n-p1-1 ) * ( p2-n )를 더해주는 경우(#2)를 수행할지 말지 결정한다.

sum += p2-n-1;

p2-n-1 개는 무조건 존재하므로 조건을 따질 필요 없이 더해준다.

 

	if(p1 == n || p2 == n) {
        	System.out.println(0); // 구간과 n이 겹치는 경우
        }else {
        	System.out.println(sum);
        }

예제 입력 3과 같이 구간과 n이 겹치는 경우에는 좋은 구간이 존재할 수 없으므로 0을 출력하고

그외에는 계산한 값을 출력하도록 한다.

 

 

 

 

 

재요약

 

4

a b d e

c

(a<b<d<e), (b<c<d)인 경우

 

집합 S의 수 중 n(=c)보다 작으면서 가장 큰 값 = p1

집합 S의 수 중 n(=c)보다 크면서 가장 작은 값 = p2

 

2가지 경우로 나누어 풀 수 있음

1. [x,y]에서 x = n(=c)인 경우

2. [x,y]에서 x < n(=c)인 경우

 

1. [n,n+1] ... [n,p2-1]까지 가능

    따라서 개수는 (p2-1)-(n+1)+1 = (p2-n-1) 개

2. [p1+1, n] .......... [p1+1, p2-1]

    [p1+2, n] .......... [p1+2, p2-1]

    ...

    [n-1, n] ............. [n-1, p2-1]    까지 가능

    따라서 개수는  { (n-1) - (p1+ 1) + 1 } x { (p2 - 1) - n + 1 } = ( n - p1 - 1 ) x ( p2 - n )

 

 

조건 1만 만족할 경우 개수는 ( p2 - n + 1)

조건 2만 만족할 경우 개수는 ( p2 - n + 1) + ( n - p1 - 1 ) x ( p2 - n )

 

집합 S에 속하는 정수와 n이 겹칠경우 0

 

 

 

 

예시

4

1 4 300 1000

59

 

집합 S의 수 중 n(=59)보다 작으면서 가장 큰 값 = 4

집합 S의 수 중 n(=59)보다 크면서 가장 작은 값 = 300

 

2가지 경우로 나누어 풀 수 있음

1. [x,y]에서 x = n(=59)인 경우

2. [x,y]에서 x < n(=59)인 경우

 

1. [59,60] ... [59,299]까지 가능

    따라서 개수는299-60+1 = 240개

2. [5, 59] .......... [5, 299]

    [6, 59] .......... [6, 299]

    ...

    [58, 59] ............. [58, 299]    까지 가능

    따라서 개수는  (58-5+1) x (299-59+1) = 13014

 

 

 

조건2를 만족하므로  240+13014 = 13254개