3273 : 두 수의 합

https://www.acmicpc.net/problem/3273

3273번: 두 수의 합

이번에 개인적인 알고리즘 공부를 하면서 두수의 합을 구할 때 공간 복잡도를 포기하고 시간복잡도를 끌어올리는 방식으로 O(N)까지 끌어올릴 수 있는 방식을 배웠다

 

 

<코드 설명>

해당 알고리즘은 두 수의 합에서 지나간 배열의 원소를 기록해놓는 방식이다

우리가 일반적으로 생각하는 방식은 O(n^2)의 방식이다.

이중 for문을 사용하여 하나하나 원하는 값을 대조해보는 것이다

물론 N^2의 알고리즘은 효율적이지 않다

(사실 N^2으로 풀고 싶었지만..... 코딩테스트 준비해야지??)

그게 다이긴 하지만, 합이 음수가 될 경우, 지나간 수를 기록하는 순서를 count연산 앞에 해서 자꾸 틀렸다

 

import java.util.*;
import java.io.*;
public class Main {

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		
		int n=Integer.parseInt(br.readLine());
		
		String input=br.readLine();
		String[] split= input.split(" ");
		
		int x=Integer.parseInt(br.readLine());
		//입력 끝
		boolean[] exist=new boolean[2000001];
		
		int count=0;
		//짝홀 나눠라
		
		for(int i=0;i<split.length;i++)
		{
			int num=Integer.parseInt(split[i]);
			
			if(x-num>0)
			{
				if(exist[x-num]==true)
					count++;
			}
					
			exist[num]=true;
		}
		System.out.println(count);
		
	}
}