[자바] 백준 1253 - 좋다 (java)

 문제 : boj1253

---

 

필요 알고리즘 개념

• 투 포인터, 이분 탐색, 해싱 등
  
  • 이하 풀이는 투 포인터 풀이이다.
• 정렬
  • 투 포인터 또는 이분 탐색 사용시엔 정렬도 필요하다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

---

 

풀이

말로만 적어보면 간단하다.

1. 입력받은 N개의 값을 정렬한다.

2. idx : 0 to N-1 에 대해 arr[idx]를 제외한 나머지 값들 중 두 개를 합쳐서 arr[idx]가 되는 경우가 존재한다면 cnt++

3. cnt를 출력한다.

 

  여기서 문제가 되는 부분은 '2'에서 두 개를 합쳐서 arr[idx]가 되는 경우가 존재하는지 확인하는 부분이다. 이걸 해결하는 방법은 해싱, 이분 탐색 등 다양하지만 내 경우엔 투 포인터 알고리즘을 사용했다. 이유는 그 이외는 'arr[idx]를 제외한 나머지 값들' 부분을 예외처리 하기 까다로워보였기 때문이다.

 

  N개의 값은 무작위로 들어오는 -10억~+10억 범위의 임의의 값이다. 이걸 정렬한 후, 가장 첫 값과 가장 뒤의 값을 각각 포인터 st와 ed로 지정한다. 이 때 sum = arr[st] + arr[ed] 이다. 그럼 경우의 수는 아래와 같다.

- sum == arr[idx] 라면 문제에서 원하는 경우를 찾은 것이다.

- sum < arr[idx] 라면 sum이 더 큰값을 가져야 하므로, st++ 를 해줘야 한다. 정렬된 데이터 이므로, st++를 해주면 sum이 증가하고 ed--를 해주면 sum이 감소한다.

- sum > arr[idx]라면 위에서 말했듯 ed--를 해주면 된다.

 

  이 때 st == idx 또는 ed == idx인 경우엔 한칸 더 움직여주면 되므로 예외처리가 간단해진다. 이걸 두 포인터가 서로 만나는 경우까지 진행해주면 된다.

private int searchCnt(int idx, int[] arr) {
    int st = 0;	// st는 처음
    int ed = arr.length-1;	// ed는 마지막
    int target = arr[idx];	// 찾고자 하는 합
    while (true) {
        if (st==idx) st++;	// 예외처리
        if (ed==idx) ed--;	// 예외처리
        if (st>=ed) break;	// 종료 조건은 두 포인터가 만날 때이다.
        int sum = arr[st]+arr[ed];	// st와 ed가 가르키는 값의 합
        if (sum == target) {	// sum == arr[idx]인 경우
            return 1;
        }

        if (sum > target) ed--;	// sum > arr[idx]인 경우
        else st++;	// sum < arr[idx]인 경우
    }
    return 0;
}

 

  위의 함수를 idx : 0 to N-1 까지 진행하면 되며, 투 포인터 자체가 O(N) 이므로, 총 시간 복잡도는 O(N^2)이고 N이 2000이므로 문제 없이 통과 가능하다.

 

---

 

코드 : github

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

public class Main {
    private int searchCnt(int idx, int[] arr) {
        int st = 0;
        int ed = arr.length-1;
        int target = arr[idx];
        while (true) {
            if (st==idx) st++;
            if (ed==idx) ed--;
            if (st>=ed) break;
            int sum = arr[st]+arr[ed];
            if (sum == target) {
                return 1;
            }

            if (sum > target) ed--;
            else st++;
        }
        return 0;
    }
    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        if (n<=2) {
            System.out.println(0);
            return;
        }
        int[] arr = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++)
            arr[i] = Integer.parseInt(st.nextToken());
        Arrays.sort(arr);

        int base = -1000000001;
        int bf = 0;
        int cnt = 0;
        for (int i = 0; i < n; i++) {
            if (base == arr[i]) {
                cnt += bf;
                continue;
            }
            cnt += bf = searchCnt(i, arr);
            base = arr[i];
        }
        System.out.println(cnt);
    }
    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}