[백준] 두 수의 합 #3273

이지성·2024년 2월 4일

백준 알고리즘 코딩

코딩테스트

목록 보기

2/8

문제 링크 : https://www.acmicpc.net/problem/3273

1. Constraints (제한 사항)

알고리즘 문제와 요구와 제한사항

문제

n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다.
ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다.
자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i < j ≤ n)을 만족하는
(ai, aj)쌍의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 수열의 크기 n이 주어진다.
다음 줄에는 수열에 포함되는 수가 주어진다.
셋째 줄에는 x가 주어진다.
(1 ≤ n ≤ 100000, 1 ≤ x ≤ 2000000)

제한

시간 제한 : 1초
메모리 제한 : 128MB

나의 생각

양의 정수 n개를 원소로 가지는 배열 (Array) 사용
원소의 자료형은 int (1 < ai < 1000000) (n과 x도)
(ai, aj)쌍의 수를 구해야하므로 반환값은 0~1000000C2
i와 j가 다르므로 같은 수를 사용하면 안 됨.

2. Ideas (문제 풀이 방식)

문제를 해결할 수 있는 방법 (최대 3개) + 시간/공간 복잡도

(1) 브루트포스 알고리즘

: 앞에서부터 배열을 순차적으로 도는 반복문 하나와,
그 수 다음을 순차적으로 도는 반복문을 사용한 이중 반복문
if문으로 두 수의 합이 같다면 cnt를 1 추가함

시간 복잡도 : O(N^2)
공간 복잡도 : O(1)

시간복잡도과 공간복잡도에 대한 정확한 이해를 돕기 위해 글을 찾아보았다.

3. Code (작성한 코드)

아이디어에서 다룬 내용을 바탕으로 구현한 코드

def find_num_pair_cnt(n: int, array: list[int], x: int) -> int:
    cnt = 0
    
    for i in range(0, len):
        for j in range(i, len):
            if nums[i] + nums[j] == target:
                cnt = cnt + 1
    
    return cnt

4. Test cases (테스트케이스)

테스트 케이스에 대해서 고민해보고, 직접 테스트해보기

9
5 12 7 10 9 1 2 3 11
13

: 프로그램을 수행하게 되면 알고리즘에 따라
합이 13인 쌍 (12, 1), (10, 3), (2, 11) 을 찾게 된다.
따라서 이 프로그램은 맞을 것이다.

하고 백준에 제출하였더니 시간 초과라는 문구를 마주했다.

5(1). 다시 생각하기

맨 처음 문제를 읽었을 때 시간과 메모리 제한을 생각하지 않았다.
이에서 발생한 문제일 것이니 1번부터 다시 생각하였다.

따라서,

시간제한을 해결하기 위해 반복문을 한 번만 사용하기로 했다.
브루트포스 알고리즘에서 반복문을 하나 제거하기 위해서 리스트 슬라이싱을 사용한다.
in 연산자를 사용하여 x에서 자신을 뺀 수가 있다면 cnt에 1을 더하기로 한다.
이번 알고리즘은 시간 복잡도가 O(N)이며, 공간 복잡도는 O(1)이다.
2번의 아이디어를 이용하여 작성한 코드이다.

def find_num_pair_cnt(n: int, array: list[int], x: int) -> int:
    cnt = 0
    
    for i in range(0, n):
        if (x - array[i]) in array[i:]:
            cnt = cnt + 1
         
    return cnt

테스트 케이스는 당연히 잘 통과했다. 이런 또 시간 초과다.

5(2). 또 다시 생각하기

검색해보니 in 연산자는 파이썬에서 O(N)의 시간복잡도를 가진다고 한다.

하나씩 검색해보는 것일텐데 이 당연한 생각을 왜 하지 못했을까?
다른 알고리즘을 생각해야 한다.

일단 공간복잡도는 128MB = 2^27B 이므로 int(4B)가 100000개? 충분하다.
시간복잡도 해결을 위해서 반복문을 한 개 사용하면서 이 문제를 해결할 수 있는 방법이 무엇일까?

일단 데이터가 정렬되어 있지 않다.
그러므로 자료의 탐색을 in과 같이 순차적으로밖에 할 수 없다.

그렇다면 자료를 정렬한다면 어떨까?
사용할 수 있는 알고리즘의 종류가 좀 더 늘어나게 된다.

혹시나 해서 sorted() 함수의 시간복잡도를 살펴보니
최악의 경우에도 O(NlogN)의 시간복잡도를 보장한다고 한다.

파이썬이 1초에 2000만번의 연산을 한다고 가정하라는 말을 보았다.

n이 100000 이하이기 때문에
O(NlogN) 정도면 1초를 통과할 수 있지 않을까.

그래서 자료구조를 정렬한 후에 어떻게 해결할 지에 대해 고민하였다.

그러다,
졍렬된 배열에서 자료를 탐색하는 시간복잡도는 O(logN)이기 때문에
단일반복문 O(N)과 O(logN)을 곱한 O(NlogN)을 통해 풀 수 있다는 결론에 도달했다.
(O(logN)인 이유는 이진탐색이 가능하기 때문이다.)

다시 코드를 짜보았다.

def find_num_pair_cnt(n: int, array: list[int], x: int) -> int:
    cnt = 0
    array = sorted(array)
    
    for i in range(n):
        start = i+1
        end = n-1
        mid = start
        
        while start <= end:
            mid = (start + end) // 2
            
            if array[mid] > x - array[i]:
                end = mid - 1
            elif array[mid] < x - array[i]:
                start = mid + 1
            else:
                cnt = cnt + 1
                break

    return cnt

테스트 케이스도 정상적으로 작동하는 것을 확인하였다. 이제는...!