[백준/JAVA] 1253번: 좋다

 

 

투 포인터 문제들

2023.04.03 - [코테/백준] - [백준/JAVA] 2018번: 수들의 합 5

2023.04.03 - [코테/백준] - [백준/JAVA] 1940번: 주몽

🔺 문제

1253번: 좋다

🔺 코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        var br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        long[] arr = new long[N];
        int cnt = 0;

        var st = new StringTokenizer(br.readLine()," ");
        for(int i = 0 ; i < N ; i++) {
            arr[i] = Long.parseLong(st.nextToken());
        }

        Arrays.sort(arr);

        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)  {
                        cnt++;
                        break;
                    }
                    else if(i == k) {
                        i++;
                    }
                    else if(j == k) {
                        j--;
                    }
                }
                else if(arr[i] + arr[j] < find) {
                    i++;
                }
                else {
                    j--;
                }
            }
        }
        System.out.println(cnt);
        br.close();
    }
}

✅ 해결 아이디어
- 투 포인터 알고리즘 (두 포인터 위치 : 양 끝!)
- 찾고자하는 값(find)을 배열의 원소에서 하나하나 살펴봄.
- 투 포인터 알고리즘 돌리는 동안, k가 서로 다른 두 수의 합인지 확인하는 조건문 필요 (28-37번째 줄)

누적합 구하는 거 아니면 두 포인터 위치는 양 끝으로 잡고 하면 되는갑다!

고로 투 포인터 두 지점은 앞으로 분리해놓고 시작하는걸로..

 

암튼 이제 투 포인터 문제 감은 잡혔다! 이제 남은 것은 복습뿐,,,

---

🔺 다른 풀이들

[BOJ] 1253번: 좋다 (Java)

[백준] 1253번 좋다 (JAVA)