[백준] 합이 0 3151 java - 투포인터

 

3가지를 고르는 것이므로 완전탐색하면 당연히 시간초과..

하나를 고정시켜 놓은 후에 투포인터를 이용해서 2개를 고르는 아이디어까지는 생각했는데

반례 케이스를 고려하지 못해서 힘들게 푼 문제다 ㅜㅜ

아래 블로그를 참고해서 아이디어를 얻었다

https://skdltm117.tistory.com/71

 

정렬 후 -> 투포인터(start, end)를 사용해서 합이 0이 되는 값을 고르면 되는데

여기서 주의해야 할 사항은

같은 값이 여러개인 경우 3가지 조건에 맞춰서 경우의 수를 세주는 것이다!

맨 처음 오답 풀이로 하면 같은 값이 여러개인 경우를 정확히 카운팅 할 수 없다.

 

1) start, end 같은 값이 여러개인 경우

2) start 같은 값이 여러개인 경우

3) end 같은 값이 여러개인 경우

 

반례)

8

-10 5 5 5 5 5 5 5

Answer: 21

출력: 6

 

 

[오답 풀이]

import java.io.*;
import java.util.*;

public class Main {
    static int solve(int start, int end, int key, int[] arr){
        int cnt = 0;
        while(start<end){
            int sum = arr[start]+arr[end];
            if(sum==key) {
                cnt++;
                start++;
            }
            else if(sum>key){
                end--;
            }else {
                start++;
            }
        }
        return cnt;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        int[] arr = new int[N];

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

        Arrays.sort(arr);

        int cnt = 0;
        for (int i = 0; i < N-1; i++) {
            cnt += solve(i + 1, N - 1, arr[i] * -1, arr);
        }

        System.out.println(cnt);

    }

}

위의 답에는 다음과 같은 문제가 있다

-sum==key인 경우 경우의 수를 나누지 않음

- else if~else 문으로 인해 시간초과 발생...

sum==key인 경우에도 인덱스를 바꿔줘야 하기 때문에

기존 방식대로 하려면 sum==key인 경우에도 start++를 추가해주거나

아래 코드처럼 if~else로 한번에 인덱스를 처리해줘야 함..

 

 

[정답 풀이]

import java.io.*;
import java.util.*;

public class Main {
    static int comb(int n){
        return n*(n-1)/2;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        int[] arr = new int[N];

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

        Arrays.sort(arr);

        long cnt = 0L;
        for (int i = 0; i < N-1; i++) {
            int start = i+1;
            int end = N-1;
            int key = arr[i]*-1;

            if(arr[i]>0)
                break;

            while(start<end){
                int sCnt = 1;
                int eCnt = 1;
                int sum = arr[start]+arr[end];
                if(sum==key) {
                    if(arr[start]==arr[end]){
                        cnt += comb(end-start+1);
                        break;
                    }
                    while(start+1<end && arr[start]==arr[start+1]){
                        sCnt++;
                        start++;
                    }
                    while(start<end-1 && arr[end]==arr[end-1]){
                        eCnt++;
                        end--;
                    }
                    cnt += sCnt * eCnt;
                }

                if(sum>key)
                    end--;
                else
                    start++;
            }
        }

        System.out.println(cnt);

    }

}