좋다 (BJ_G4_1253)

1. 문제 링크

 

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

 

 

---

 

2. 나의 코드

메모리: 14540 kb
시간: 144 ms
코드 길이: 1248 B
시간 복잡도 : O(NlogN) 
설명
- 정렬을 사용한다(logN)
- 투포인터를 사용한다.(N)

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

public class BJ_1253 {

    static int N, cnt;
    static int[] nums;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        nums = new int[N];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            nums[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(nums);
        for (int i = 0; i < N; i++) {
            solve(i);
        }
        System.out.println(cnt);
    }

    public static void solve(int target) {
        int s = 0;
        int e = nums.length - 1;

        while (s < e) {
            if (nums[s] + nums[e] == nums[target]) {
                if (s == target) s++;
                else if (e == target) e--;
                else {
                    cnt++;
                    return;
                }
            } else if (nums[s] + nums[e] < nums[target]) {
                s++;
            } else {
                e--;
            }
        }
    }
}

 

---

 

3. 정답 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class P1253_좋은수 {
  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 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);
    for (int k = 0; k < N; k++) {
      long find = A[k];
      int i = 0;
      int j = N - 1;
      while (i < j) {  // 투포인터 알고리즘 
        if (A[i] + A[j] == find) {
          // find는 서로 다른 두 수의 합이여야됨을 체크
          if (i != k && j != k) {
            Result++;
            break;
          } else if (i == k) {
            i++;
          } else if (j == k) {
            j--;
          }
        } else if (A[i] + A[j] < find) {
          i++;
        } else {
          j--;
        }
      }
    }
    System.out.println(Result);
    bf.close();
  }
}

 

---

 

4. 배운 점

- 연속된 합(가변)을 구하는 문제 같은 경우는 포인터 두개를 시작점에 위치시킨다.

- 두 수의 합을 구하는 문제는 포인터 두개를 양 옆에 위치시킨다.

- 만약 두 수의 합이 N을 찾았다면 s++, e--를 진행시킨다.