java 1059번 좋은 구간 (백준)

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		int n, m;
		Scanner scan = new Scanner(System.in);
		n = scan.nextInt();                              //배열의 요소의 개수
		int[] sort = new int[n];                         //배열 생성
		for(int i=0; i<n; i++) sort[i] = scan.nextInt(); //배열에 넣기
		m = scan.nextInt();                              //특정한 값 입력 받기
		int i, j, key, gap = n/2;                        //shell sort
		while(true) {
			if(gap%2==0) gap++;
			for(i=gap; i<n; i++) {
				key = sort[i];
				for(j=i-gap; j>=0; j-=gap) {
					if(key < sort[j]) sort[j+gap] = sort[j];
					else break;
				}
				sort[j+gap] = key;
			}
			if(gap == 1) break;
			gap >>= 1;
		}
		
		int left=1, right=0, ans=0, flag = 0; //좋은 구간의 왼쪽값, 오른쪽 값, 범위의 개수, 오른쪽값의 갱신여부
		
		if(sort[n-1] < m) ans = -1; //만약 입력 받은 수 보다 특별한 수가 
		
		for(i=0; i<n; i++) { //좋은 구간의 왼쪽과 오른쪽 값 찾기
			if(flag == 1) break; //오른쪽 값을 갱신을 했다면 반복문을 종료
			if(sort[i] == m) { //배열에 특별한 수가 있다면, 반드시 좋은 구간은 없다
				ans = -1;
				break;
			}
			
			if(sort[i] < m) left = sort[i]+1; //왼쪽 값
			if(m < sort[i]) {                 //오른쪽 값
				flag = 1;
				right = sort[i]-1;
			}
		}
		
		if(ans >= 0 && right != 0) { //좋은 구간 구하기
			ans += (right-m) * (m-left+1); //(왼쪽 구간부터 특별한 수까지의 개수) * (특별한 수의 다음 수부터 오른쪽 구간의 수까지의 개수)
			ans += (m-left); //(왼쪽구간부터 특별한 수전까지의 개수)
		}
		else ans = 0;
		System.out.print(ans);
	}
}

 
풀이 : 정렬
 
배열로 여러개의 수를 입력 받은 다음.
그런다음 특별한 수 (문제에서는 n)을 이용하여 좋은 구간의 개수를 찾아야 합니다.
좋은 구간을 알기 위해선 모든 좋은 구간들 중 가장 왼쪽의 값과, 오른쪽의 값을 찾아야 합니다.
 
배열을 정렬 한다음,
특별한 수보다 작으면서 가장 큰 값을 찾고 이 값에 +1 한 것을 좋은 구간의 가장 왼쪽의 값으로 지정하며,
특별한 수보다 크면서 가장 작은 값을 찾고 이 값에 -1 한 것을 좋은 구간의 가장 오른쪽 값으로 지정합니다.
 
만약 배열에 있는 수와 특별한 수가 같다면, 좋은 구간은 존재하지 않습니다.
또한 배열에서 가장 큰 값이 특별한 수보다 작아도 좋은 구간은 존재하지 않습니다.
 
위에서 구한 왼쪽, 오른쪽 값을 이용하여 좋은 구간의 개수를 구해야 한다.
 
여러 가지 방법이 존재하겠지만
 
저는
1. 좋은 구간의 오른쪽이 특별한 수보다 큰 경우
2. 좋은 구간의 오른쪽이 특별한 수 인 경우
 
이 두가지의 경우를 구한다음 더했습니다
 

파란색 5 -> 4 로 정정합니다. 잘못적었습니다

1. 의 경우는 (특별한 수 - 가장 왼쪽의 수 +1) * (가장 오른쪽의 수 - 특별한 값의 수) 을 하여 구간의 개수를 구할 수 있으며
2. 의 경우는 (특별한 수 - 가장 왼쪽의 수)가 구간의 개수 입니다.
 
이 1과 2의 경우를 더한 값이 전체 좋은 구간의 개수입니다.
 
https://www.acmicpc.net/problem/1059

1059번: 좋은 구간