008. 좋다(백준1253번)

문제

문제 분석하기

문제안에서 얻을 수 있는 정보

• 시간제한 2초 = 약 2억번의 연산안에 해결해야 한다.
• $N = 2000$ 즉, $N^2$ 의 시간복잡도 보다 작은 시간복잡도를 가진 알고리즘으로 접근해야한다.
• "좋은 수" 가 되는 수는 연산에서 제외시켜야 한다.
• 수의 위치가 다르면 값이 같아도 다른 수이다.

손으로 풀어보기

두 수...? 투포인터를 이용해 접근해보자!

투 포인터 이동 원칙 ( i=start(min), j=end(max), k=좋은 수 )

A[i] + A[j] > K j--; // 좋은 수 보다 크니깐 큰 값을 왼쪽이동 = 두 수의 합 감소
A[i] + A[j] < K i++; // 좋은 수 보다 작으니 작은 값 오른쪽이동 = 두 수의 합 증가
A[i] + A[j] == K count++; continue;

슈도코드 작성하기

N(수의개수 저장)
A배열 선언
for(N만큼) {
	A(N개의 값들 저장)
}

A배열 정렬

result(결과가 담길 변수)

for(int i=0; i<N; i++) {
	find = A[i]; // 인덱스로 값에 접근
	start = 0;
	end = N-1;
	
	while(start<end) {
		if(start + end == find) {
			if(start != i && end != i) {
				result++;
				braek;
			}else if(start == i) {
				start++;
			}else if(end == i) {
				end--;
			}
		}else if(A[start] + A[end] > find) {
			start++;
		}else if(A[start] + A[end] < find) {
			end--;
		}
	}
}

코드 구현하기

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
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 ) );
		BufferedWriter bw = new BufferedWriter( new OutputStreamWriter( System.out ) );
		
		int N = Integer.parseInt( br.readLine() );
		int[] A = new int[ N ];
		
		StringTokenizer st = new StringTokenizer( br.readLine() );
		for ( int i = 0; i < N; i++ ) {
			A[ i ] = Integer.parseInt( st.nextToken() );
		}
		
		Arrays.sort( A );
		
		int result = 0;
		for ( int i = 0; i < N; i++ ) {
			int find = A[i];
			int start = 0;
			int end = N - 1;
			
			while ( start < end ) {
				if(A[start] + A[end] == find) {
					if(start != i && end != i) {
						result++;
						break;
					}else if(start == i) {
						start++;
					}else if(end == i){
						end--;
					}
				}else if(A[start] + A[end] < find) {
					start++;
				}else if(A[start] + A[end] > find) {
					end--;
				}
			}
		}
		
		bw.write( String.valueOf( result ) );
		
		bw.flush();
		bw.close();
	}

} // end