백준 1253 좋다

https://www.acmicpc.net/problem/1253

투포인터 슬라이딩 윈도우 문제이다.

완전탐색으로 문제를 해결하면,
N의 범위가 2000이고 값 2개에 대해 각각 2000번 루프를 돌리고 N번을 반복해야 하니
O(n^3)의 시간복잡도로 시간초과가 난다.

하지만 투포인터로 접근하면 원소를 탐색하는데 n번, 루프를 n번 반복이니
O(N^2)의 시간복잡도로 해결할 수 있다.

1) 파이썬 코드

def solve(idx):
    global ans
    s,e = 0,length-1
    value = arr[idx]
    while s < e:
        p_sum = arr[s] + arr[e]
        if s == idx:
            s += 1
            continue
        if e == idx:
            e -= 1
            continue
        if p_sum == value:
            ans += 1
            return
        if p_sum < value:
            s += 1
        elif p_sum > value:
            e -= 1

n = int(input())
arr = list(map(int,input().split()))
arr.sort()
length = len(arr)
ans = 0
for i in range(n):
    solve(i)
print(ans)

2) 자바 코드

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

public class boj1253 {
    private static final int INF = 1000000000;
    private static int n;
    private static int[] list;
    private static int ans;

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();

        n = Integer.parseInt(br.readLine());
        list = new int[n];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            list[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(list);
        for (int i = 0; i <n; i++) {
            solve(i);
        }
        System.out.println(ans);
    }

    static void solve(int idx) {
        int s = 0;
        int e = list.length -1;
        int value = list[idx];
        while (s < e) {
            int p_sum = list[s] + list[e];
            if (s == idx) {
                s += 1;
                continue;
            }
            if (e == idx) {
                e -= 1;
                continue;
            }
            if (p_sum == value) {
                ans += 1;
                return;
            }
            if (p_sum<value) s += 1;
            else if(p_sum>value) e -= 1;
        }
    }

}