99클럽 코테 스터디 10일차 TIL (챌린저): [백준][Java] 1253 좋다 - 골드4

 

문제 보기

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

 

 

풀이

1. 실패 소스

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

public class Main {

  public static void main(String[] args) throws IOException {

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    int N = Integer.parseInt(br.readLine());
    StringTokenizer st = new StringTokenizer(br.readLine());
    int[] arr = new int[N];
    int[] nums = new int[1000000001];
    for(int i = 0; i < N; i++) {
      int num = Integer.parseInt(st.nextToken());
      arr[i] = num;
      nums[num]++;
    }

    Arrays.sort(arr);

    int count = 0;
    for(int i = 0; i < N; i++) {
      for(int j = 0; j < i - 1; j++) {
        int num = arr[i] - arr[j];
        if(nums[num] > 1) {
          count++;
          break;
        } else if(nums[num] > 0 && num != arr[j]) {
          count++;
          break;
        }
      }
    }

    bw.write(count + "\n");

    bw.flush();
    bw.close();
  }
}

맨 처음엔 나올 수 있는 모든 정수 길이의 배열을 만들고

몇 번 나왔는지 확인하려고 했으나 이는 메모리를 간과한 풀이였다.

이 방식으로 진행할 경우 O(N^2)이나 N은 2000이기 때문에 4,000,000 정도로 빨리 끝낼 수 있었을 텐데... 아쉽다.

 

2. 투포인터

그래서 투포인터 알고리즘을 도입하였다.

역시 두 번 반복문을 돌 것 이기 때문에 시간 복잡도는 O(N^2)이다.

  private static boolean twoPointer(int[] arr, int i, int n, int num) {
    int start = 0;
    int end = n - 1;
    while(start < end) {
      int sum = arr[start] + arr[end];
      if(sum == num) {
        if(start == i) {
          start++;
        } else if(end == i) {
          end--;
        } else {
          return true;
        }
      }
      if(sum > num) {
        end--;
      } else if(sum < num) {
        start++;
      }
    }
    return false;
  }

투포인터 알고리즘은 이분 탐색과 모양이 비슷하나 성질은 다르다.

배열의 양 쪽에서 순회를 하기 때문에 N^2의 순회시간을 N^1로 바꿔준다는 장점이 있다.

 

 

전체 코드

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

public class Main {

  public static void main(String[] args) throws IOException {

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    int N = Integer.parseInt(br.readLine());
    StringTokenizer st = new StringTokenizer(br.readLine());
    int[] arr = new int[N];
    for(int i = 0; i < N; i++) {
      arr[i] = Integer.parseInt(st.nextToken());
    }

    Arrays.sort(arr);
    int count = getCount(N, arr);

    bw.write(count + "\n");
    bw.flush();
    bw.close();
  }

  private static int getCount(int N, int[] arr) {
    int count = 0;
    for(int i = 0; i < N; i++) {
      if(twoPointer(arr, i, N, arr[i])) {
        count++;
      }
    }
    return count;
  }

  private static boolean twoPointer(int[] arr, int i, int n, int num) {
    int start = 0;
    int end = n - 1;
    while(start < end) {
      int sum = arr[start] + arr[end];
      if(sum == num) {
        if(start == i) {
          start++;
        } else if(end == i) {
          end--;
        } else {
          return true;
        }
      }
      if(sum > num) {
        end--;
      } else if(sum < num) {
        start++;
      }
    }
    return false;
  }
}

 

 

GitHub 링크

https://github.com/MetroDefro/CodingTest_AutoSave/tree/main/%EB%B0%B1%EC%A4%80/Gold/1253.%E2%80%85%EC%A2%8B%EB%8B%A4

CodingTest_AutoSave/백준/Gold/1253. 좋다 at main · MetroDefro/CodingTest_AutoSave