백준 1253: 좋다 [골드 Ⅳ / Java]

출처 : https://www.instiz.net/name_enter/69260559

 

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

1253번: 좋다

---

 

 

Solution
투 포인터, 정렬

 

 

모든 각 배열 요소에 대해서 nC₂ 연산을 할 수 없으니,

정렬을 해서 투 포인터를 진행한다.

 

 

 

1  4  7  8  9  10  11  12  15
s                          e

 

N이 20 이면 1 + 15 < 20 이므로 s를 늘려준다.

 

1  4  7  8  9  10  11  12  15
      s                    e

 

7 + 15 > 20 이므로 e를 줄여준다.

 

1  4  7  8  9  10  11  12  15
      s                e

 

7 + 12 < 19 이므로 s를 늘려준다.

 

1  4  7  8  9  10  11  12  15
         s             e

 

 

 

 

 

해당 문제에서 왼쪽 포인터와 오른쪽 포인터가 페르마의 밀실처럼 조여올 때 다음과 같이 경우를 나눌 수 있다.

 

1. 왼쪽 값 + 오른쪽 값 == 해당 값일 때

    1 - 1. 둘 다 해당 값과 다를 때 : 답

    1 - 2. 왼쪽 값이 해당 값과 같을 때 :

             음수인 해당 값과 오른쪽 값이 0 일 때이다. 왼쪽에서 오던 인덱스를 늘려 해당 값에서 벗어난다.

    1 - 3. 오른쪽 값이 해당 값과 같을 때 :

             왼쪽 값이 0 일 때와 양수인 해당 값일 때이다. 오른쪽에서 오던 인덱스를 줄여 해당 값에서 벗어난다.

2. 해당 값이 작을 때 : 왼쪽 인덱스를 늘려, 값이 커지게 한다.

3. 해당 값이 클 때 : 오른쪽 인덱스를 줄여, 값이 작아지게 한다. 

 

 

 

 

Comment

 

 

투 포인터에서 두 포인터만 필요하다면

정렬된 상태에서 포인터를 증가시키는 것은 값이 늘어나는 효과를,

포인터를 감소시키면 값이 줄어드는 효과가 있다.

 

(하지만 투 포인터로 무슨 연산을 하느냐 혹은 정렬 여부에 따라

포인터를 증가시키는 것이 무조건 값이 증가하는 효과가 있는 것은 아니다.

 

투 포인터 사이 구간 합을 구하는 문제에서는 포인터를 증가시키는 것이 증가, 감소 효과가 있다.

백준 2018번: 수들의 합 5 [실버 Ⅴ / Java])

 

 

 

 

위 문제에서 값을 증가시킬 때 s를 증가시키고

값을 감소시킬 때 e를 감소시킨다.

 

 

1  4  7  8  9  10  11  12  15
      s                e

 

그럼 e를 증가시키면 값을 늘리는 데도 사용할 수 있지 않을까 엉뚱한 생각을 잠깐 했는데,

s=7, e=12 일 때

e=15 이었을 때는 이미 s=1, 4, 7 과 연산을 했고, 7과의 합이 컸기 때문에 12로 줄여진 것이다.

7+ 15 > 20 으로 답이 아님을 확인했는데 다시 돌아가면 무한 반복에 빠질 것이다.

 

즉, 포인터 e는 값을 줄이는데만 사용되어야 한다.

 

s를 왼쪽으로 보내서 값을 줄이는데도 사용할 수 있지 않을까라는 생각에도 같은 논리로 답을 할 수 있겠다.

 

 

 

투 포인터에서 목표는 두 개의 포인터로 값을 감소와 증가시키며 관찰하는 것이다.

이때 하나의 포인터는 하나의 역할만 해야한다.

그럼 s는 무조건 증가시키고 e는 무조건 감소시켜야 하느냐는 생각을 해본다면,

s를 감소시키고 e를 증가시키면 당연히 끝으로 가기 때문에 잘못된 생각이다.

 

 

 

 

Code

 

 

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

public class Main {

    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        long arr[] = new long[N];  //10억 숫자까지 나올 수 있어서.
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) arr[i] = Long.parseLong(st.nextToken());
        Arrays.sort(arr);

        int cnt = 0;
        for (int t = 0; t < N; t++) {
            long num = arr[t];
            int i = 0, j = N - 1;

            while (i < j) {
                if (arr[i] + arr[j] == num) {
                    if (i != t && j != t) {
                        cnt++;
                        break;
                    } else if (i == t) i++;   // -arr[K]과 0
                    else if (j == t) j--;     // 0과 arr[K]
                } else if (arr[i] + arr[j] < num) i++;
                else j--;
            }
        }

        System.out.println(cnt);
    }

}