[코딩테스트] 백준 1253 자바

백준 1253

백준 1253 문제

시간 복잡도

해당 문제는 어떤 수를 기준으로 두 수의 합을 구해야하는 문제이다.

이를 구하기 위해서는 삼중 반복문을 사용해야 하는데, 최악의 경우 n이 2000이면 시간 제한을 초과하게 된다.

따라서 어떤 수를 구하는 반복문 안에서 시간 복잡도 O(n)를 갖는 투 포인터 알고리즘은 사용하면 시간 복잡도 O(n2)로 답을 구할 수 있다.

import java.io.*;
import java.util.*;

public class Boj1253 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine()); // 수의 갯수
        StringTokenizer st = new StringTokenizer(br.readLine());
        long[] arr = new long[n]; // 수를 담을 배열 선언
        int result = 0; // 좋은 수의 갯수

        // 배열 초기화
        for (int i = 0; i < n; i++) {
            arr[i] = Long.parseLong(st.nextToken());
        }

        Arrays.sort(arr); // 오름차순 정렬 O(n log 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의 값이 찾는 값이면 조건에 안 맞기 때문에
                        i++; // 포인터를 오른쪽으로 이동
                    } else { // 포인터 j의 값이 찾는 값이면 조건에 안 맞기 때문에
                        j--; // 포인터를 왼쪽으로 이동
                    }
                } else if (arr[i] + arr[j] < find) { // 두 수의 합이 찾는 값보다 작으면
                    i++; // 포인터 i를 오른쪽으로 이동
                } else { // 두 수의 합이 찾는 값보다 크면
                    j--; // 포인터 j를 왼쪽으로 이동
                }
            }
        }
        System.out.println(result); // 좋은 수의 갯수 출력
        br.close();
    }
}

풀이

1. 입력되는 수들을 배열에 담아 초기화한다.
2. Arrays.sort(arr)로 배열을 오름차순 정렬한다.
3. 배열을 반복하면서 찾을 값 find를 할당하고, 양끝에 포인터가 만나기 전까지 반복한다.
4. 두 포인터 값들의 합이 찾는 값이고, 두 포인터 값들이 찾는 값이 아니라면 조건에 성사하기 때문에 좋은 수에 추가한다. result++
5. 두 포인터 값들의 합이 찾는 값이지만 포인터 i가 찾는 값의 인덱스 k와 같다면 포인터 i를 오른쪽으로 이동한다.
6. 두 포인터 값들의 합이 찾는 값이지만 포인터 j가 찾는 값의 인덱스 k와 같다면 포인터 j를 왼쪽으로 이동한다.
7. 두 포인터 값들의 합이 찾는 값보다 작으면 포인터 i를 오른쪽으로 이동시켜 두 포인터의 값들의 합을 증가시킨다.
8. 두 포인터 값들의 합이 찾는 값보다 크면 포인터 J를 왼쪽으로 이동시켜 두 포인터의 값들의 합을 감소시킨다.
9. 반복문이 종료되면 좋은 수의 갯수를 출력한다.