BOJ3273 두 수의 합*

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

3273번: 두 수의 합

숫자의 제한선이 주어진다면 숫자의 범위 만큼 배열을 만들자!

또한 문자열 문제라면 HashMap을 적극 활용하자!

import java.io.*;
import java.util.*;
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.valueOf(br.readLine());
		int[] input = new int[n];
        String[] temp = br.readLine().split(" ");
        int i =0;
        for(String t : temp){
            input[i++] = Integer.parseInt(t);
        }
        int x = Integer.valueOf(br.readLine());
        
        Arrays.sort(input);
        
        int count = 0;
        
        for(i =0; i<n; i++){
            if(input[i]>x/2) break;
            for(int j=i+1;j<n;j++){
                if(input[i]+input[j]==x){
                    count++;
                }        
                if(input[i]+input[j]>x){
                    break;
                }
            }
        }
        
        bw.write(Integer.toString(count));
        bw.flush();
	}
}

 

 

숫자의 제한선이 주어진다면 숫자의 범위 만큼 배열을 만들자!

위의 방법은 빅오를 정확히 알 수 없다.

 

import java.util.Scanner;

class Main
{
    public static void main (String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] a = new int[N];
        for (int i = 0; i < N; i++)
            a[i] = sc.nextInt();
        int X = sc.nextInt();

        int[] cnt = new int[1000001];
        for (int i = 0; i < N; i++)
            cnt[a[i]]++;

        long ans = 0;
        for (int i = 1; i <= (X - 1) / 2; i++)
            if (X - i <= 1000000)
                ans += (long)cnt[i] * cnt[X - i];
        System.out.println(ans);
    }
}