백준 [자바 java] 1253번 : 좋다

문제설명

n개의 수가 주어지고, 그 중 어떤 수가 다른 두 수의 합으로 나타낼 수 있으면 그 수를 좋다라고 한다.

n개의 수 중 좋은 수의 갯수는?

 

풀이

이 문제는 1년전 실패했었다..

다시 보니까 그 이유가 좀 보였다!

일단 3퍼에서 자꾸 틀렸습니다가 나왔는데 그 이유는 배열을 정렬하고 첫번째 수를 전혀 고려하지 않았기 때문이다. 

하지만 이렇게 하면

0 0 0 0일때 배열 내의 가장 작은 수도 좋은 수가 될 수 있는데 이를 간과해버린다.

 

또 60프로대에서 계속 틀렸습니다가 나왔는데 이건 좋은 수는 서로 다른 두 수를 더했을 때 좋다고 할 수 있는데, 투포인터를 하는 과정에서 지금 탐색하고 있는 수까지 포함시켜버렸다.

예를 들어 2가 좋은 수인지 탐색하는데 2+0을 확인하고 좋은수라고 인식한 것이다.

 

그거 말고는 투포인터로 풀면 특별히 어려운 문제는 아니었다.

package org.example;
import java.util.*;
import java.io.*;
import java.math.*;


public class Main {

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

    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 ans = 0;

    for(int i = 0;i<n;i++){
      int left = 0;
      int right = n-1;

      while(left < right){
        if(left == i){
          left++;
          continue;
        }
        if(right == i){
          right--;
          continue;
        }
        if(arr[left] + arr[right] == arr[i]){
          ans++;
          break;
        }
        else if(arr[left] + arr[right] < arr[i]){
          left++;
        }
        else{
          right--;
        }
      }
    }

    System.out.println(ans);

  }
}

 

하하..