99클럽 코테 스터디 4일차 TIL 투포인터(좋다)

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

 

사용 알고리즘

투 포인터

 

아이디어

1. 배열 정렬

2. 모든 각각의 수에 대해 투포인터 탐색

3. s, e가 현재 탐색하는 수인 경우 제외하고

4. 좋다를 만족하는 수면 cnt++

5. s, e의 합이 탐색하는 수보다 작으면 s++;, 크면 e--;

 

유의점

1. s, e가 현재 탐색하는 수인 경우 제외 조건을 걸지 않아서 틀렸었음,, (s == i 면 s++;, e == i 면 e--;)

 

제출코드

package BOJ.BinarySearch;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class BOJ_1253_좋다 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n];

        StringTokenizer st = new StringTokenizer(br.readLine());
        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; i++){
            int now = arr[i];
            int s = 0;
            int e = n - 1;
            while(s < e){
                int sum = arr[s] + arr[e];
                // s, e가 i인 경우 제외
                if(s == i) s++;
                else if(e == i) e--;
                // 좋다를 만족 하는 수
                else if(sum == now) {
                    cnt++;
                    break;
                }
                else  if(sum > now) e--;
                else s++;
            }
        }
        System.out.println(cnt);
    }
}