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;
    }
}