[백준] 1253번 좋다 (JAVA)

---

 

투 포인터를 이용한 문제다.

투 포인터를 둘다 시작 지점으로 놨더니

생각할게 너무 많아지고, 시간복잡도도 증가했다.

 

투포인터를 시작지점, 끝점으로 양쪽으로 옮겨서 구현했더니 간단하게 풀렸다.

 

구간합이 아니면 투포인터를 시작지점에 두지 말아야 겠다.

 

---

코드구현

 

import java.io.*;
import java.util.*;
import java.util.function.*;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
   
    public static void main(String[] args) throws IOException {
        int count = Integer.parseInt(br.readLine());
        int[] arr = new int[count];
 
        int idx = 0;
        StringTokenizer st = new StringTokenizer(br.readLine());
        while(st.hasMoreTokens()){
            arr[idx++] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(arr);
        int goodNumber = 0;
 
        
        for(int i = 0; i<arr.length; i++) {
            int findNumber = arr[i];
 
            // 투포인터
            int s = 0; // 시작지점
            int e = arr.length - 1; // 배열 끝지점
            int sum = 0;
 
 
            while(s < e){
                sum = arr[s] + arr[e];
                if(sum == findNumber){
                    if(i == s)
                        s++;
                    else if(e == i)
                        e--;
                    else{
                        goodNumber++;
                        break;
                    }
                }
 
                if(arr[s] + arr[e] > findNumber) //find 보다 크면 e--
                    e--;
                else if(arr[s] + arr[e] < findNumber) // find보다 작으면 s++
                    s++;
 
 
            }
        }
        System.out.println(goodNumber);
    }
}
 
 
 

 

 

---