백준 1253 좋다 - java/파이썬 풀이

 

풀이

정렬 후 투포인터를 이용

 

유의할점

처음에 정렬 후 투포인터를 각각 0 과 i-1(타겟 인텍스 i)로 잡았는데 틀렸다고 나와 한참 고민했다.

입력조건을 보면  (|Ai| ≤ 1,000,000,000, Ai는 정수)으로 음수 입력 또한 가능하며 음수가 입력된다면

타겟인덱스보다 뒤에 있는 수를 더해야 타켓에 부합할 수도 있다.

 

자바

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
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));
        int N = Integer.parseInt(br.readLine());
        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 count = 0;
        //타겟은 모든 어레이 요소이다
        for (int i = 0; i < N; i++) {
            int target = arr[i];
            int left = 0;
            int right = N-1;
            while (left < right){
                int sum = arr[left] + arr[right];
                //두 포인터 요소의 합이 타겟과 일치하는 경우
                if (sum == target){
                	//포인터가 타겟의 인덱스와 일치하지 않는다면 (자기자신을 더하는 경우가 아닐때)
					//결과값을 하나 증가하며 반복문을 빠져나온다
                    if (left != i && right != i){
                        count++;
                        break;
					//자기 자신을 더하는 경우일때 인덱스를 하나 옮긴뒤 계속 실행한다
                    } else if(left == i){
                        left++;
                    } else if (right == i){
                        right--;
                    }
                    //타겟보다 두 포인터 요소의 합이 작다면 왼쪽(작은쪽)의 포인터를 증가시키고
                } else if (sum < target){ 
                    left++;
                    //타겟보다 클 경우 큰쪽의 포인터를 감소시킨다.
                } else {
                    right--;
                }
            }
        }
        //결과값 프린트
        System.out.println(count);
    }
}

 

파이썬 

import sys
input = sys.stdin.readline

n = int(input())
arr = list(map(int, input().split()))
arr.sort()
count = 0

for i in range(n):
    index_s = 0
    index_e = n-1
    while index_s < index_e:
    	//두 포인터 요소의 합이 타겟과 같을때
        if arr[index_s] + arr[index_e] == arr[i]:
        	//각각의 포인터가 타겟인덱스가 아니라면 결과값을 증가시킨 후 반복문 탈출
            if index_s != i and index_e != i:
                count += 1
                break
            //두 포인터중 하나가 타겟인덱스라면 (자기자신을 더하는 경우) 포인터 변경
            elif index_s == i:
                index_s += 1
            elif index_e == i:
                index_e -= 1
        //각각의 포인터 요소의 합이 타겟보다 작다면 작은쪽의 포인터를 +1
        elif arr[index_s] + arr[index_e] < arr[i]:
            index_s += 1
		//포인터 요소의 합이 타겟보다 크다면 큰쪽의 포인터를 -1
        else:
            index_e -= 1
//결과값 프린트
print(count)