1253 좋다

다른 사람 블로그를 참고해서 풀었다.

 

두 포인터를 활용하였다.

 

1) 풀이 예시

 

5 =N

1 2 3 5 8 => number 배열에 오름차순 정렬하여 입력.

 

를 생각해보자.

 

2) 3이 좋다 조건을 만족할까?

 

 

먼저 3이 좋다 조건을 만족하는지 생각해보자.

일단 두 포인터로 변수 one, two 를 사용한다.

 

처음에

one = 0, two = N-1 = 4

=> number[one] = 1, number[two] = 8

=> sum = number[one] + number[two] = 9

 

3을 변수 value 에 입력한다.

=> value = 3

 

value (3) < sum(9) 이므로,

sum 값을 줄여야 value 에 가까워진다.

 

number 배열을 오름차순 정렬했기 때문에, sum 을 줄이려면 two 인덱스를 감소시켜야 한다.

=> two--

 

그러면

one = 0, two = 3

=> number[0] = 1, number[two] = 5

=> sum = 6

value = 3

 

value < sum 이므로 역시 two 인덱스를 줄여나가면서 value = sum 을 만족할 때까지 하면 된다.

 

 

3) 5가 좋다 조건을 만족할까?

위의 예시를 이어서 풀이한다.

 

5 

1 2 3 5 8

 

이 경우도 시작은 one = 0, two = 4

sum = number[one] + number[two] =  9

value = 5

 

value < sum 이므로 two 인덱스를 줄인다.

one = 0, two = 3

그런데, 좋다 조건을 만족하려면 자기 자신이 아닌 다른 두개의 합을 구해야 한다.

그런데 숫자 5의 인덱스는 3으로 two 와 같다.

그래서 이 경우는 two를 한 번 더 감소시킨다.

 

one = 0, two = 2

sum = number[one] + number[two] =  4

 

value > sum 이므로, sum 을 증가시켜야 value 에 가까워질 수 있다.

그래서 이번에는 one 인덱스를 증가시킨다.

one = 1, two = 2

sum = number[one] + number[two] =  5

sum = value 이므로 숫자 5는 좋다 조건을 만족한다.

 

4) 최종 코드

 

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 number []= new int [N];
	StringTokenizer st = new StringTokenizer(br.readLine(), " ");

	
	for(int i=0; i<N; i++) {
		number[i] = Integer.parseInt(st.nextToken());
	}
	
	
	Arrays.sort(number);
	
	int count = 0;
	
	for(int i=0; i<N; i++) {
		
		int one = 0;
		int two = N-1;
		
		while(one<two) {
		
			if(one==i) {
				one++;
				continue;
			}
			
			if(two==i) {
				two--;
				continue;
			}
			
			int sum = number[one]+ number[two];
			int value = number[i];
			
			if(value == sum) {
				count++;
				break;
			}
		
		
			if(value<sum ) {
				two--;
			}else if(value>sum) {
				one++;
			}
		}
	}
	
	
	System.out.println(count);
	
	}
}

 

참고 블로그 : https://coder-in-war.tistory.com/entry/BOJ-JAVA1253-%EC%A2%8B%EB%8B%A4

[ BOJ ][JAVA][1253] 좋다