3151 합이 0
[ 1 ]
예제를 한 경우 생각해보면,
-5 -5 1 1 1 1 4 4 4 4 4
1)
주어진 예제에서 학생들의 코딩 실력을 오름차순 정렬한다.
-5 -5 1 1 1 1 4 4 4 4 4
2)
for 문을 돌리는데 투포인터도 같이 사용한다. (left, right)
2-1) i = 0 , left =1, right = 10
즉,
0번째 값 = -5 ,
left = i+1 = 1
-> 1번째 값 = -5
right = N-1 = 10
-> 10 번째 값 = 4
이 때 세가지 경우의 합 = (-5) + (-5) + 4 = -6
이 경우는, 0을 만들기에 더 작은 값이므로 left 를 증가시켜서 다시 합을 구한다.
2-2) i = 0 , left =2, right = 10
0번째 값 = -5 ,
left = 1 +1 = 2
-> 2번째 값 = 1
right = N-1 = 10
-> 10 번째 값 = 4
이 경우의 합= (-5) + 1 + 4 = 0
이 경우
문제에서 찾는, 합이 0이 된 경우이다.
그러면 이제 left 를 1개 더 증가시켜서, 또 합이 0 이 되는 경우를 찾아보면 된다.
(right 를 1개 줄여도 됨)
2-3) i = 0 , left =3, right = 10
이 경우
0번째 값 = -5 ,
left =3
-> 3번째 값 = 1
right = N-1 = 10
-> 10 번째 값 = 4
이 경우도 합이 0이 되는 경우이며,
-5 + 1 + 4 = 0 인,
위와 같은 경우이다.
즉 이런 경우가 반복된다.
따라서,
같은 값이 반복되는 경우를
따로 처리해주면 된다.
즉, 1이 4개 있고,
4가 5개 있으므로,
4*5 = 20 만큼 똑같은 경우가 반복된다.
따라서 정답은,
i = 0 일때 20개의 경우,
i =1 일 때 20개의 경우가 있으므로
총 40개가 정답이 된다.
[ 2 ]
다른 예시를 살펴보면,
-10 5 5 5 5 5 5
이런 경우가 있을 수 있다.
그러면 for문을 돌렸을 때,
1) i = 0 , left = 1, right = 6
-> 0번째, 1번째, 6번째 값을 더하면
(-10) + 5 +5 =0 이다.
이 경우는 left의 값과, right의 값이 5로 같은 경우이다.
즉, 5가 총 6개 있는데,
6개 중 2개를 조합으로 선택하는 경우이다.
따라서 n * (n-1) /2 로 계산을 하면 되며,
6 * 5 / 2= 15 가 정답이 된다.
이런식으로 풀면 된다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
int N = Integer.parseInt(st.nextToken());
st = new StringTokenizer(br.readLine(), " ");
int input[] = new int[N];
for(int i=0; i<N; i++) {
input[i] = Integer.parseInt(st.nextToken());
}
long count = 0;
//오름차순
Arrays.sort(input);
for(int i=0; i<N-1; i++) {
int left = i+1;
int right = N-1;
int a =1;
int b= 1;
while(left < right) {
a=1;
b=1;
int sum = (input[i] + input[left] + input[right]);
if(sum== 0) {
if(input[left] == input[right]) {
count+=combination(right-left+1);
break;
}
while(left+1<N && (input[left] == input[left+1])) {
a++;
left++;
}
while(right-1>=0 && (input[right] == input[right-1])) {
b++;
right--;
}
count+=a*b;
left++;
}else if(sum>0) {
right--;
}else if(sum<0) {
left++;
}
}
}
System.out.println(count);
}
public static int combination(int n) {
return n*(n-1)/2;
}
}