코딩 테스트 [자료구조] - '좋은 수' 구하기

주어진 N개의 수에서 다른 두 수의 합으로 표현되는 수가 있다면 그 수를 '좋은 수'라고 한다. N개의 수 중 좋은 수가 총 몇 개인지 출력하시오.

---

입력

1번째 줄에 수의 개수 N(1 ⪯ N ⪯ 2,000), 2번째 줄에 N개의 수의 값(Ai)이 주어진다(|Ai| ⪯ 1,000,000,000, Ai는 정수).

출력

좋은 수의 개수를 출력한다.

예제 입력
10	// 수의 개수
1 2 3 4 5 6 7 8 9 10

예제 출력
8

---

1단계 - 문제 분석하기

N의 개수가 최대 2,000이라 가정해도 좋은 수 하나를 찾는 알고리즘의 시간 복잡도는 N2보다 작아야 한다. 만약 시간 복잡도가 N2인 알고리즘은 사용하면 최종 시간 복잡도는 N3이 되어 시간 내에 문제를 풀 수 없기 때문이다.
따라서 좋은 수 하나를 찾는 알고리즘의 시간 복잡도는 최소 O(nlogn)이어야 한다. 정렬, 투 포인터 알고리즘을 사용한다.
단 정렬된 데이터에서 자기 자신을 좋은 수 만들기에 포함해서는 안된다.

2단계 - 손으로 풀어 보기

1 수를 입력받아 배열에 저장한 후 정렬한다

2 두 포인터 i, j를 배열 A 양쪽 끝에 위치시키고 조건에 적합한 투 포인터 이동 원칙에 때라서 탐색을 수행한다. 판별 대상이 되는 수는 K라고 가정한다.

투 포인터 이동 원칙

• A[i] + A[j] > K : j--;
• A[i] + A[j] < K : i++;
• A[i] + A[j] == K : i++; j--; count++;

3 2 단계를 배열의 모든 수에 대하여 반복한다. 즉 K가 N이 될때까지
반복하여 좋은 수가 몇 개인지 센다.

3단계 - sudo코드 작성하기

N(수의 개수)
A(수 데이터 저장 배열)

for(N만큼 반복하기) {
	A배열에 데이터 저장하기;
}

A 배열 정렬하기;

for(k -> 0 ~ N) {
	변수 초기화(포인터 i, 포인터 j, 찾고자 하는 값 find);
    
    while(i < j){
    	if(A[i]+A[j] == find)
        	if(i != k && j != K)
            	좋은 수의 개수 증가;
                while문 종료;
            else if(i == k)
            	i 값 증가;
            else if(j == k)
            	j 값 감소;
        else if(A[i] + A[j] < find)
        	i 값 증가;
        else if(A[i] + A[j] > find)
        	j 값 감소;
	}
}

좋은 수의 개수 출력;

4단계 - 코드 구현하기

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

public class Q8 {
    public static void main(String[] args) throws NumberFormatException, IOException{
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(bf.readLine());
        long A[] = new long[N];
        StringTokenizer st = new StringTokenizer(bf.readLine());
        for(int i = 0; i < N; i++){
            A[i] = Long.parseLong(st.nextToken());
        }
        Arrays.sort(A);
        int count = 0;

        for(int k = 0; k < N; k++){
            int i = 0;
            int j = N-1;
            long find = A[k];

            while(i < j){
                if(A[i] + A[j] == find){
                    if(i != k && j != k){
                        count += 1;
                        break;
                    } else if (i == k) {
                        i++;
                    } else if (j == k){
                        j--;
                    }
                } else if (A[i] + A[j] < find) {
                    i++;
                } else if (A[i] + A[j] > find) {
                    j--;
                }
            }
        }
        System.out.println(count);
        bf.close();
    }
}

---

• Do it! 알고리즘 코딩테스트 자바 편