문제
집합 S와 양의 정수 M이 주어진다. [A, B] (A ≤ M ≤ B, A ≥ 1)에서 A와 B 모두 S에 포함되지 않는 구간을 좋은 구간이라 한다. M이 S에 포함되면 좋은 구간의 수는 0이다. 그렇지 않으면 M보다 작은 S의 최댓값을 left, M보다 큰 S의 최솟값을 right라 할 때, A는 left+1 ~ M, B는 M ~ right-1 범위에서 선택 가능하다.
입력
첫째 줄에 집합의 크기 N이 주어진다. (1 ≤ N ≤ 50)
둘째 줄에 집합 S의 원소 N개가 주어진다. (1 ≤ 원소 ≤ 1000)
셋째 줄에 M이 주어진다. (1 ≤ M ≤ 1000)
출력
좋은 구간의 수를 출력한다.
예제
입력:
4
1 4 7 10
6출력:
8풀이
핵심 아이디어: M이 S에 포함되면 0을 출력한다. 그렇지 않으면 M을 기준으로 왼쪽의 가장 가까운 S 원소와 오른쪽의 가장 가까운 S 원소를 찾아 구간 경우의 수를 계산한다.
- 배열을 정렬한다.
- M보다 작은 S 원소 중 최댓값
left, M보다 큰 S 원소 중 최솟값right를 찾는다. M이 S에 없으면left = 0,right = 987654321로 초기화한다. - A의 선택 가능 범위:
left+1~M→L = M - left - 1 + 1 = M - left가 아닌L = M - left - 1개 (A가 M일 때도 포함, B가 M일 때도 포함)- A 선택 수:
M - (left+1) + 1 = M - left→ 코드에서는L = M - left - 1로 계산 후 A=M인 경우를 별도 처리 - 실제로 A:
left+1~M(총M - left개), B:M~right-1(총right - M개) - A와 B가 모두 M인 경우(A=B=M) 1개를 빼야 하므로:
(M-left) × (right-M) - 1 - 코드에서는
L = M - left - 1,R = right - M - 1,answer = L + R + L*R으로 동치 계산
- A 선택 수:
- M이 S에 있으면 0을 출력한다.
코드
package com.ssafy.an.day199;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Day195BOJ1059좋은구간정렬 {
public static void main(String[] args) throws Exception {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(in.readLine());
int N = stoi(st.nextToken());
int arr[] = new int[N];
st = new StringTokenizer(in.readLine());
for (int i = 0; i < arr.length; i++) {
arr[i] = stoi(st.nextToken());
}
st = new StringTokenizer(in.readLine());
int M = stoi(st.nextToken());
Arrays.sort(arr);
int left = 0, right = 987654321;
boolean find = false;
for (int i = 0; i < arr.length; i++) {
if (arr[i] > M) {
right = Math.min(right, arr[i]);
} else if (arr[i] < M) {
left = Math.max(left, arr[i]);
} else {
find = true;
break;
}
}
int L = (M - left - 1);
int R = (right - M - 1);
int answer = L + R + (L * R);
if (find)
System.out.println(0);
else
System.out.println(answer);
}
static int stoi(String s) {
return Integer.valueOf(s);
}
}복잡도
- 시간: O(N log N) — 정렬 후 선형 탐색
- 공간: O(N) — 입력 배열 저장