백준 1253: 좋다(java/python)

문제

---

풀이

 

오름차순 정렬한 배열 A[]에 투 포인터 기법을 사용하여 풀이할 수 있다.

 

낮은 인덱스부터 탐색할 left와 높은 인덱스부터 탐색할 right 포인터를 선언하고, for문을 순회하며 오름차순 정렬한 A[i]를 순서대로 탐색한다. 현재 요소(A[i])가 sum = A[left] + A[right]보다 크면 right을 1 감소시키고, A[i] < sum이면 left를 1 증가시키는 것이 기본 원리이다. 해당 과정을 위해서는 A[i]를 먼저 정렬해야 함에 유의하자.

for(int i=0; i<N; i++) {
	int left=0;
	int right=N-1;
			
	while(left<right) {
		int sum=A[left]+A[right];
				
		if(sum>A[i]) {
			right--;
		}
		else if(sum<A[i]) {
			left++;
		}
		else {
			right--; left++;
			count++;
			break;
		}
	}
}

left 포인터는 항상 right 포인터의 왼쪽에(낮은 인덱스에) 위치해야 하므로 while문의 조건을 left<right로 둔다.

 

여기에 "어떤 수가 다른 수 두 개의 합으로 나타낼 수 있다면" 의 조건을 위해 left나 right가 i와 같을 경우 반복을 건너뛰는 작업을 추가하면 알고리즘은 완성된다.

if(left==i) {
	left++;
	continue;
}
else if(right==i) {
	right--;
	continue;
}

 

전체 코드

 

1. java

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());
		
		StringTokenizer st=new StringTokenizer(br.readLine());
		int[] A=new int[N];
		for(int i=0; i<N; i++) {
			A[i]=Integer.parseInt(st.nextToken());
		}
		
		Arrays.sort(A);
		
		int count=0;
		
		for(int i=0; i<N; i++) {
			int left=0;
			int right=N-1;
			
			while(left<right) {
				int sum=A[left]+A[right];
				
				if(left==i) {
					left++;
					continue;
				}
				else if(right==i) {
					right--;
					continue;
				}
			
				if(sum>A[i]) {
					right--;
				}
				else if(sum<A[i]) {
					left++;
				}
				else {
					right--; left++;
					count++;
					break;
				}
			}
		}
		System.out.println(count);
	}
}

 

2. python

N = int(input())
A = list(map(int, input().split()))

A.sort()

count = 0

for i in range(N):
    left = 0
    right = N-1

    while left < right:
        if left == i:
            left += 1
            continue
        elif right == i:
            right -= 1
            continue

        sum = A[left] + A[right]

        if sum > A[i]:
            right -= 1
        elif sum < A[i]:
            left += 1
        else:
            right -= 1
            left += 1
            count += 1
            break

print(count)