[백준 - 3151][GOLD 4][해설 X] - 합이 0 (JAVA)

문제 링크

---

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

 

문제

---

Elly는 예상치 못하게 프로그래밍 대회를 준비하는 학생들을 가르칠 위기에 처했다. 대회는 정확히 3명으로 구성된 팀만 참가가 가능하다. 그러나 그녀가 가르칠 학생들에게는 큰 문제가 있었다. 코딩 실력이 좋으면 팀워크가 떨어지고, 팀워크가 좋을수록 코딩 실력이 떨어진다. 그리고 출전하고자 하는 대회는 코딩 실력과 팀워크 모두가 중요하다.

Elly는 그녀가 가르칠 수 있는 모든 학생들의 코딩 실력을 알고 있다. 각각의 코딩 실력 Ai는 -10000부터 10000 사이의 정수로 표시되어 있다. 그녀는 팀워크와 코딩 실력이 모두 적절한 팀을 만들기 위해, 세 팀원의 코딩 실력의 합이 0이 되는 팀을 만들고자 한다. 이러한 조건 하에, 그녀가 대회에 출전할 수 있는 팀을 얼마나 많이 만들 수 있는지를 계산하여라.

N명의 학생들의 코딩 실력 Ai가 -10000부터 10000사이의 정수로 주어질 때, 합이 0이 되는 3인조를 만들 수 있는 경우의 수를 구하여라.

 

입력

---

입력은 표준 입력으로 주어진다.

첫 번째 줄에 학생의 수 N이 입력된다. 두 번째 줄에 N개의 그녀가 가르칠 학생들의 코딩 실력인 Ai가 주어진다.

 

출력

---

표준 출력으로 그녀가 고를 수 있는 팀의 수를 하나의 정수로 출력한다.

 

해결 코드

---

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        int[] skill = new int[N];

        StringTokenizer st = new StringTokenizer(br.readLine());

        for(int i=0;i<N;i++){
            int val = Integer.parseInt(st.nextToken());
            skill[i] = val;
        }

        Arrays.sort(skill);
        long count = 0;
        
        //가장 첫번째 수를 고른다
        for(int i=0;i<skill.length;i++){
            if(skill[i] > 0){
                break;
            }

            int left = i+1;
            int right = N-1;
            
            //나머지 부분에서 2개를 고른다
            while(left < right){
                int sum = skill[i] + skill[left] + skill[right];
                long leftSameCount = 1;
                long rightSameCount = 1;
                
                //나머지 2숫자를 찾은 경우
                if(sum == 0){
                    //2번째와 3번째 수가 같으면 2번째~3번째 사이의 모든 수가 같으므로 해당 영역 중에 2개를 고르는 경우와 같다.
                    if(skill[left] == skill[right]){
                        long length = right - left + 1;

                        count += length*(length-1)/2;
                        break;
                    }
                    //2번째 다음 수가 2번째 수와 같다면 다음 숫자는 세지 않고 +1하면 된다.
                    while(left + 1 < right && skill[left]  == skill[left+1]){
                        leftSameCount++;
                        left++;
                    }
                    //3번째 다음 수가 3번째 수와 같다면 다음 숫자는 세지 않고 +1하면 된다.
                    while(right -1 > left && skill[right]  == skill[right-1] ){
                        rightSameCount++;
                        right--;
                    }

                    //2번째 수를 고르는 경우의 수 * 3번째 수를 고르는 경우의 수 
                    count += leftSameCount*rightSameCount;
                }

                //합이 0보다 크면 큰 숫자를 줄여야한다
                if(sum > 0){
                    right--;
                }
                //합이 0보다 작으면 작은 숫자를 키워야한다.
                else{
                    left++;
                }
            }
        }

        System.out.println(count);
    }
}

 

 

실행 결과

---

 

팁

---

• N이 10,000인 경우 이중 for문을 통한 탐색을 진행할 시 N^2/2 = 5천만이기 때문에 시간제한 1초 이하는 해결할 수 있다.
• 중복된 값을 스킵할 수 있다면 시간 효율을 줄일 수 있다