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

문제설명

문제

N개의 수 중에서 어떤 수가 다른 수 두 개의 합으로 나타낼 수 있다면 그 수를 “좋다(GOOD)”고 한다.

N개의 수가 주어지면 그 중에서 좋은 수의 개수는 몇 개인지 출력하라.

수의 위치가 다르면 값이 같아도 다른 수이다.

 

입력

첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수)

 

출력

좋은 수의 개수를 첫 번째 줄에 출력한다.

문제풀이

시간복잡도

N의 최대 개수가 최대 2000이라 가정해도 좋은 수 하나를 찾는 알고리즘의 시간복잡도는 N^2보다 작아야 한다. 따라서 알고리즘의 시간 복잡도는 최소 O(nlongn)이어야 한다. 따라서 투 포인터 알고리즘을 사용하면 된다.

 

1. n, result , startIndex , endIndex list,  선언2. for문을 돌면서 list 0인덱스부터 마지막 인덱스 까지 while문을 통해 확인3. while문은 startindex + endindex 합이 for문 i번째 인덱스와 비교하여 같으면 출력4. 조건에 정렬된 데이터에 자기 자신을 좋은 수 만들기에  미포함이기 때문에 한번더 걸러준다. (startIndex와 i가 같거나, endIndex와 i가 같은경우)

 

package doit_java;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;

public class doit_8_좋은수구하기 {
    public static void main(String[] args) throws IOException {
        //N, list 입력받기
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());
        ArrayList<Integer> list = new ArrayList<>(n);
        for (int i = 0; i < n; i++) {
            list.add(Integer.parseInt(st.nextToken()));
        }

        Collections.sort(list);
        int result = 0;
        for(int i=0; i<n; i++) {
        int startIndex = 0;
        int endIndex = n - 1;
        long find = list.get(i);
        while (startIndex < endIndex) {
            //find는 서로 다른 두 수의 합이어야 함을 체크
            if(list.get(startIndex) + list.get(endIndex) == find){
                if(startIndex!=i && endIndex!=i){
                    result++;
                  break;
                }
                else if(startIndex==i){
                    startIndex++;
                }
                else{endIndex--;}
            }
            else if(list.get(startIndex)+ list.get(endIndex)<find){
                startIndex++;
            }
            else{endIndex--;}

        }
    }
        System.out.println(result);


    }



}

 

 

투 포인터 알고리즘이 궁금하면 확인 하시길 ! 

[알고리즘] Two Pointers 알고리즘이란?