[백준 / Java] 3273. 두 수의 합

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

3273번: 두 수의 합

 

---

💻 풀이 결과

 

💯 최종 코드

import java.util.Scanner;

/*
 * 시간 복잡도를 생각해서
 * O(n²)을 만들면 안된다!
 */
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        // 입력
        int n = sc.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = sc.nextInt();
        }
        int x = sc.nextInt();

        // tmp 의 범위를 생각해야한다... 
        boolean[] num = new boolean[2000000];
        int cnt = 0;
        for (int i : arr) {
            // tmp 가 음수일 수도 있음
            // 왜? x가 a보다 더 작을 수 있잖아
            int tmp = x - i;

            // tmp 가 내 앞에 있었나? 확인한다.
            // 있었으면? 1쌍 추가
            // 중요 : tmp 가 음수일 수도 있다는 걸 생각한다
            if (tmp > 0 && num[tmp]) {
                cnt++;
            }
            // 숫자의 존재 여부 체크
            num[i] = true;
        }

        System.out.println(cnt);
    }
}

 

💢 틀린 이유

• 주어지는 숫자 x보다 수열에 포함된 수가 더 큰 경우를 고려하지 못했다.
• 코드에서 tmp의 범위를 잘 고려하지 못했다.

💡 깨달은 점

1. 주어진 n의 크기를 생각해서 시간 복잡도 고려하기

• 시간 복잡도가 O(n²)보다 작도록 구현

2. 구현 아이디어!

• 두 수의 합을 구하기 위해서 배열을 탐색하는 알고리즘인 경우에 O(n)의 시간 복잡도를 가지도록 구현
• 큰 범위의 숫자 배열을 생성하고 차례대로 수열을 탐색하는 데, 이 때 앞에서 체크한 수를 기억하는 아이디어로 구현