[백준][JAVA] 3273 - 두 수의 합

이른 아침에 산책을 나가서 아침밥을 먹다가 심심해서 예전에 실패했던 백준 문제들을 둘러보았습니다.
실버3 문제 하나를 빠른 방법으로 풀게 되어서 공유하려고 합니다.

 

---

문제 링크

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

 

 

개요

"주어진 배열에서 서로 다른 원소 두 개의 합이 X가 되는 경우의 수를 구하시오".

 

알고리즘을 처음 배울 때 조합으로 접근했다가 어리둥절했던 문제입니다.

'분명 배운 대로 했는데 왜 통과를 못하는 거지?'

물론 이제는 순열, 조합과 같은 완전탐색보다 훨씬 빠른 알고리즘이 많다는 걸 깨달았으니

더 빠른 풀이방법을 생각해 낼 줄 알아야겠죠.

 

 

조합으로 풀 경우

시간 제한이 1초인 문제입니다. 배열의 크기는 최대  100,000으로 주어집니다.

배열에서 2개의 원소를 찾기 위해서는 이중 반복문을 순회하게 되고, O(N^2) 시간복잡도를 갖게 됩니다.

N^2 = 100,000 * 100,000 = 10,000,000,000이고,  O(N^2) 알고리즘이면 그 정도 크기에 준하는 연산 횟수가 발생하게 될 것입니다.

 

1초 내에 어림잡아 1억 번(100,000,000)의 연산만 가능할 텐데, 필요한 연산 횟수가 과하게 많습니다.

 

[제출 결과]

 

* 실패 코드는 게시글 맨 아래에 정답 코드와 함께 올려두겠습니다.

 

 

 

O(N)으로 풀 수 없을까?

배열을 순회하면서 특정 원소 a를 만났을 때,

“앞으로 X-a에 해당하는 원소가 존재한다면 정답 갯수를 1개 늘린다”라고 접근.

이 방법이라면 100,000번 내외의 연산으로 단 한번만 배열을 순회하면서 정답을 구할 수 있습니다.

[✅ 정답 코드]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main_3273 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[] arr = new int[N];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
           arr[i] = Integer.parseInt(st.nextToken());
        }
        int X = Integer.parseInt(br.readLine());
        boolean[] cache = new boolean[X];

        int result = 0;

        for (int a : arr) {
            if(a >= X)
                continue;
            // 모든 원소는 반드시 음수가 아니라 자연수이므,로 X보다 큰 값은 정답에 포함될 수 없습니다.
		        // 모든 원소는 1보다 크거나 같으므로 순서쌍 (X, 0)이라는 정답은 존재하지 않습니다.
		        // 따라서 a == X인 경우도 제거합니다.

            if(cache[a])
                result++;
                // 2. 현재 값이 cache에 true로 체크되어 있다면 정답 갯수를 1만큼 늘립니다.
            else
                cache[X - a] = true;
		            // 1. 구하고자 하는 수 X에서 현재 원소를 뺀 값을 cache에 true로 체크합니다. 
        }
        System.out.println(result);
    }
}

 

 

[제출 결과]

 

 

 

아래는 조합으로 풀었던 실패 코드이니 참고해서 보시면 되겠습니다. 

 

[❌실패 코드]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
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());
        StringTokenizer st = new StringTokenizer(br.readLine());
        int[] input = new int[N];
        for (int i = 0; i < N; i++) {
            input[i] = Integer.parseInt(st.nextToken());
        }
        int X = Integer.parseInt(br.readLine());
        int result = 0;

        for (int i = 0; i < N; i++) {
            for (int j = i; j < N; j++) {
                if(input[i] + input[j] == X){
                    result++;
                }
            }
        }
        System.out.println(result);
    }
}

 

 

---

 

코드와 관련된 피드백이나 질문이 있으시면 댓글 부탁드립니다.