[JAVA] 백준 q1253 - 좋다

1253번: 좋다



의식의 흐름

두 포인터 사용해서 배열 다 돌리면 되겠는데? -> 오답

알고보니 두 수를 합할 때 target으로 잡은 수는 두 수에 포함이 안되어야 하는데 그 부분을 확인하지 않았다.. 그것만 고치니까 정답

 

풀이

1. 배열에 수 담은 후 정렬

2. 배열 0 ~ N까지 차례대로 target으로 잡고 두 수로 나타낼 수 있는지 확인

• 두 포인터가 가리키는 수들의 합 > target) 큰 수 가리키는 포인터 왼쪽으로
• 두 포인터가 가리키는 수들의 합 < target) 작은 수 가리키는 포인터 오른쪽으로
• 두 포인터가 가리키는 수들의 합 == target
  • 두 포인터가 가리키는 수들 중 target이 없는 경우) '좋은 수'
  • 두 포인터가 가리키는 수 중 작은 수 == target) 작은 수 가리키는 포인터 오른쪽으로
  • 두 포인터가 가리키는 수 중 큰 수 == target) 큰 수 가리키는 포인터 왼쪽으로

 

코드

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

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()); // 수의 개수
        long[] nums = new long[N];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=0;i<N;i++)
            nums[i] = Long.parseLong(st.nextToken());
        Arrays.sort(nums); // 오름차순 정렬

        int goodCnt = 0;
        for(int k=0;k<N;k++){
            long target = nums[k];
            int i = 0;
            int j = N-1;

            while(i<j){
                long sum = nums[i]+nums[j];
                if(sum>target)
                    j--;
                else if(sum<target)
                    i++;
                else{ // 합이 target과 같은 경우
                    if(i!=k && j!=k){ // nums[i]나 nums[j]가 nums[k]이면 안됨
                        goodCnt++;
                        break;
                    }
                    else if(i==k)
                        i++;
                    else if(j==k)
                        j--;
                }
            }
        }

        bw.write(Integer.toString(goodCnt));
        bw.flush();
    }
}