[JAVA] '좋은 수' 구하기 (백준 1253번)

 

유형)  자료구조

제한)  2초

문제)  주어진 N개의 수에서 다른 두 수의 합으로 표현되는 수가 있다면 그 수를 '좋은 수'라고 한다. N개의 수 중 좋은 수가 총 몇 개인지 출력하시오. 단, 정렬된 데이터에서 자기 자신을 좋은 수 만들기에 포함하면 안된다.

 

// ----------- 문제: 08 '좋은 수' 구하기 ----------
// 1번째 줄: 수의 개수N (1 <= N <= 2,000)
// 2번째 줄: N개의 수 (1 <= N <= 1,000,000,000 정수만 가능)
 
 
// ----------- 입력 & 결과 ----------
10                    // 10개의 수 입력
1 2 3 4 5 6 7 9 10 8  // 숫자 나열 <--- 배열arr에 저장
 
 
// ----------- 공식 ----------
/*
    투 포인터 이동 원칙
    1) 투 포인터 i,j를 배열 A 양쪽 끝에 위치시키고 조건에 적합한 투 포인터 원칙을 활용해 탐색을 수행
    2) 변수 k는 판별의 대상이 되는 수
 
    arr[i] + arr[j] > k: j--;   
    arr[i] + arr[j] < k: i++; 
    arr[i] + arr[j] == k: i++; j--; count++; // 프로세스 종료
  
*/ 
 
 
// ----------- 코드 ----------
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Test {
    public static void main(String[] args) throws NumberFormatException, IOException {
        
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(bf.readLine()); // 수의 개수
        int Result = 0;
        long arr[] = new long[N]; // 수 데이터 저장할 배열
        StringTokenizer st = new StringTokenizer(bf.readLine());
        
        // 데이터 형 변환 후 arr에 저장.
        for(int i = 0; i < N; i++) {
            arr[i] = Long.parseLong(st.nextToken());
        }
        Arrays.sort(arr); // 배열 오름차순 정렬
        
        /* 
        for (long i : arr) {
            System.out.print(i+" ");
        }
        System.out.println("<-- 정렬 후");
        */
        
        // 판별 대상인 k를 0번부터 N까지 반복
        for(int k = 0; k < N; k++) {
            long find = arr[k]; // 찾고자하는 값
            int i = 0;
            int j = N - 1;
            
            // 투 포인터 알고리즘
            while(i < j) {
                if(arr[i] + arr[j] == find) {
                    if( i != k && j != k) {
                        Result++;
                        break;
                    } else if (i == k) {
                        i++;
                    } else if (j == k) {
                        j--;
                    }
                } else if (arr[i] + arr[j] < find) {
                    i++;
                } else {
                    j--;
                }
            }
        }
        System.out.println(Result); // 좋은 수 개수 출력
        bf.close();
    }
}
 
 

 

 

< console result >