[백준] 두 수의 합 [왜 여기까지만 생각했을까.. JAVA]

투 포인터

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

3273번: 두 수의 합

 

설명

 실패했던 문제 중 가장 의미 있게 풀어낸 문제라고 생각해서 기록을 남겨보려고 한다. 이번 문제는 투 포인터에 관련된 문제다. 최근 들어 시간 복잡도를 계산하는 연습을 틀리더라도 최대한 정확하게 해 보려고 노력하고 있다. 그래서 시간 복잡도가 어떻게 되는지와 어떤 방식으로 생각을 해볼 수 있는지 작성해보려고 한다. 

 

 투 포인터를 알아차리기 까지 그리 오래 걸리지 않았지만, 그것 보다 더 중요한 게 왜 투 포인터로 풀 수 있는지를 생각해 보는 게 문제를 푸는 것보다 더 의미가 있기 때문에, 투 포인터 말고 시간 복잡도가 더 큰 알고리즘으로 풀었을 때 어떻게 되는지를 설명하려 한다. 아래는 문제의 조건을 간략하게 정리해 본 것이다.

 

 

1. n개의 '서로 다른 양의 정수'로 이루어진 '수열'이 있다. 1 <= n <= 100000

2. a(i)의 값 즉 수열의 각 원소의 값은 1<= a(i) <= 1000000.

3. 자연수 x가 주어졌을 때, ai + aj = x (1 <= i < j <= n) 만족하는 쌍을 구해야 한다.

4. x의 범위는 1<= x <= 2000000.

 

 

 첫 번째 조건 부터 살펴보자. n개의 '서로 다른 양의 정수'로 이루어진 수열이 있다고 했다. 먼저 수열이라고 한다면, 수가 나열되어 있는 것을 의미한다고 볼 수 있다. 그리고 그러한 수열의 값들은 서로 다른 양의 정수로 이루어져 있기 때문에 0과 음의 정수는 포함하지 않는다. 정수의 체계는 음의 정수, 0, 양의 정수로 이루어져 있기 때문이다. 따라서 n개의 서로 다른 값으로 이루어진 수열은 자연수로만 이루어진 값으로 구성이 되어 있다는 것을 파악해 볼 수 있다. 그럼 테스트 케이스의 조건에서도 0과 음의 정수가 포함된 값은 있을 수 없다.

 

 두 번째 조건, 각 원소의 크기는 1보다 크거나 같고, 100만보다 작거나 같다. 여기에서도 친절하게 알려주고 있듯, 1보다 크거나 같기 때문에 위 첫 번째 조건에서 이미 작성했던, 0과 음의 정수의 값은 포함하지 않는다.

 

 세 번째 조건, 자연수 x가 주어졌을때, 두 수열의 값의 합이 x가 되어야 한다는 것을 알 수 있고, 그때 i, j 즉 '인덱스의 범위' 는 1보다 크거나 같고 n보다 작거나 같다. 따라서 1보다 크거나 같고, 100만보다 작거나 같은 값으로 구성이 될 수 있다. 또 i, j는 대소 관계가 명확하다. i인덱스는 항상 j인덱스 보다 작다. 작거나 같은 게 아니라 작은 것이다. 즉 i는 절대로 j와 같은 인덱스인 경우가 존재하지 않고 i 가 j 보다 큰 경우는 있을 수 없다는 것을 의미한다.

 

 네 번째 조건, x의 범위는 두 수열의 값의 합으로 이루어진 값을 의미한다고 볼 수 있고, 각 수열의 값이 최대 100만까지가 주어질 수 있기 때문에 100만 + 100만 = 200만이 가장 큰 값이 될 수 있다는 것을 파악해 볼 수 있다. 따라서 조건은 1보다 크거나 같고, 200만 보다 작거나 같다. 최소 조건인 1은 수열의 값이 가장 작을 때가 1과 2일 수밖에 없다. 1과 1일 수 없는 이유는 '서로 다른 양의 정수'로 이루어졌기 때문에 가장 작은 1이 두개 존재할 수 없다. 그렇다면 1이 존재하고 그다음 작은 수인 2가 존재할 때 가장 작게 되고, 그럼 최소 가장 작은 값일 때는 3이 된다는 것을 알 수 있다.

 

 조건을 순서대로 나열 하면서 어떤 조건이 있는지 파악해 보았다. 그럼 이걸 해결하기 위해 시간 복잡도가 O(N^2)인 알고리즘을 생각해 보았다고 해보자. 그렇다면 아래와 같은 알고리즘일 것이다.

 

for (int i = 0; i < n; i++) {
	for (int j = i + 1; j < j + 2; j++) {
   		if (arr[i] + arr[j] == x) {
        		cnt++;
        } 
    }
}

 

 

 위 알고리즘은 완전 탐색을 이용해 답을 구하는 과정이다. 근데 과연 저 코드가 옳을까? 위 코드에서 놓친 부분은 두 가지가 있다.

먼저, 세 번째 조건에 위배 된다. 세 번째 조건을 다시 보면, i < j라는 조건이 있다. 즉 i 인덱스는 j인덱스보다 작다는 것을 의미하지만, 서로 연속되어야 한다는 조건은 어디에도 찾아볼 수 없다. 연속된다는 것은 i가 1이라고 한다면, j는 2인 인덱스 간의 관계를 의미한다. 하지만 이러한 조건은 어디에서도 볼 수 없으며, i = 1이라면 j = 3.. 4.. 5.. 6 이어도 만족을 하기 때문에, 무작정 i < j 보다 작다고 해서, 연속을 전제로 설정하면 안된다는 것이다.

 

  두 번째로 잘못된 것은 위 전제 조건으로 인해 쌍의 개수가 정확하지 않게 된다. 다시 말해 i = 1이고 j = 3인 조건이 x를 만족한다고 하면, 위 코드를 바탕으로  i = 1일 때, j = 2이므로, 그 어떤 순간에서도 만족하는 x를 찾을 수 없다.

 

 결국 i < j 보다 작다고 하여 연속을 전제로 설정 했기에 발생된 문제이다. 이걸 예제 입력 1 케이스에 적용해 보면 x = 13일때 절대로 13을 만족하는 x를 찾을 수 없다. 그렇다면 이 문제를 어떻게 올바르게 해결해 볼 수 있을까?

 

시간 복잡도

 완전 탐색을 생각해 보기전에, 시간 복잡도를 계산해 봤다면, 아마 완전 탐색으로는 풀 수 없다는 것을 알 수 있었을 것이다. 그래서 한번 계산해 보자. 먼저, n은 10만 개의 수열이 존재할 수 있고, 완전 탐색을 이용해서 풀어내겠다고 한다면 10만 개의 수열을 한번 루프를 돌 때마다. 두 번째 루프에서도 만족하는 j를 찾기 위해 위 코드가 아닌 j를 모두 찾아 보겠다고 한다면 또 10만 개의 케이스를 전부 검사를 해 보아야 할 것이다. 시작은 i + 1부터 시작하며  j는 결국 j < n; 이 된다. 따라서 그 시간 복잡도는 O(N * N )만큼의 시간이 소요 되며, 빅오 표기에 의해 O(N^2)만큼의 시간이 걸리게 된다. 

 

 따라서 완전 탐색을 이용해서 풀게 되면 100억에 가까운 연산량으로 인해 100초라는 시간이 걸리게 되어, 1초 안에 통과할 수 없다는 것을 이해해 볼 수 있다.

 

 그러면, O(nlogn), O(n), O(logn), O(1)중 하나로 풀어내야 한다는 의미가 되는데, 선형시간으로 풀어볼 수 있을 만한 알고리즘인 투 포인터 알고리즘을 생각해 보자. 투 포인터 알고리즘을 생각해 봤다면, 현재 주어진 수열의 상태로는 end를 줄이게 되어, 이전 포스팅에서도 언급했었던 이중 포문과 투 포인터의 차이와 다를 바 없는 시간 복잡도를 갖게 된다. 따라서 포인터가 방향을 바꾸지 않고, 타깃 넘버를 구해야 한다는 것을 유념해야 한다.

 

 처음에 생각해낸 건, 최소 조건과 최대 조건의 합 조건을 생각했다. 수열이 가지는 각각의 값들은 서로 다른 양의 정수로 이루어졌기 때문에, 서로 같은 정수들이 존재하지 않아 a(i) + a(j)의 합은 각각의 수에 대해서, 서로 다른 값들을 가진다는 것을 의미한다. 그렇다면 수열 중에서 가장 작은 값이 있을 것이고, 가장 큰 값이 존재할 것이다. 가령 [1, 2, 3] 같은 수열 또한 가장 작은 값과 가장 큰 값이 존재한다. 이걸 바탕으로 가장 작은 값은 1 + 2 = 3 이 될 것이고, 가장 큰 값은 2 + 3 = 5가 된다. 따라서 우리가 찾아야 하는 x의 값은 이 범위 내에 존재 하게 된다는 것을 찾아볼 수 있었다. 따라서 예를 들었던 배열에서는 3 <= x <= 5 사이의 값을 가져야 한다는 것을 의미한다.

 

 두 번째로 생각했던 건, 만약 x를 13이라고 하자. 그럼 두 수의 합이 13이 되는 것을 찾아본다면 1 + 12, 2 + 11, 3 + 10... 과 같이 구할 수 있다. 서로 다른 수를 만족하기 때문에 위 방법대로 보면 구하는 방법에는 큰 문제가 없어 보인다. 그럼 이제 두 가지 아이디어를 어떻게 응용해 볼 수 있을까 하다가 배열을 정렬을 하여 가장 작은 값과 가장 큰 값을 더해 나가면 어떻게 될까? 라는 생각을 했었다. 그래서 예제 입력 1에 대입해 본 결과 올바른 값을 찾을 수 있었다. 하지만 여기서 내가 간과한 점이 있다. 

 

 만약 배열을 정렬 했을때, 가장 작은 값과 + 가장 큰 값의 합이 x를 만족하지 못하는 경우가 있을 수 있다는 기본 적인 조건을 위배했다. 위 13이 타깃넘버인 경우 배열을 정렬했을 때 [1..... 12] 이런 경우라면 분명히 13을 만족한다. 하지만 [1.... 11]인 경우는 만족하지 않는다. 따라서 start는 증가하고 end는 무작정 감소시키게 되면, 찾을 수 없게 된다.

 

 그래서 start, end를 어떻게 다뤄볼 수 있을까 하다. 생각이 나지 않아 아이디어를 참고 하던 중 '합의 범위'를 다시 한번 생각해 보게 한 아이디어가 있었다. 합의 범위는 생각 해보면 위에 첫 번째 생각했던 아이디어를 바탕으로 start, end를 조절하는 아이디어다.

 

 예를 들어 두 개의 수가 있다고 해보자. 그럼 두 개의 수 중에서 배열이 오름차순으로 정렬이 되어 있을 때, 뒤 end 포인터가 가리키는 값은 배열 내에서 앞에 있는 값들보다 비교적 큰 값들로 구성이 되어 있을 것이고, start 포인터가 가리키는 값은 비교적 end포인터가 가리키는 값보다는 작은 값을 가리키게 될 것이다. 그러면 만약에 두 수의 합이 x보다 작거나 크다면 어떻게 될까? 라는 생각을 확장해 볼 수 있다.

 

 만약 두 수의 합이 x보다 큰 경우를 생각해보자. x = 13이라고 하고, 두 수가 1 + 14라고 하면, 두 수의 합은 15가 된다. 그러면 x 보다 큰 수를 갖게 된다. 그럼 이 상황에서 end를 가만히 두고, start만 옮긴다고 해보자. 서로 양 끝에서 포인터가 출발하기 때문에, 현재 1이라는 값은 가장 작은 값을 가리키고 있고 14는 가장 큰 값을 가리키고 있다. 그럼 start를 증가시키면 1보다 큰 값들로만 구성이 되어 있기 때문에 점점 x보다 더 큰 값을 가지게 되어 x보다 멀어지는 값만을 갖게 된다. 그래서 두 수의 합이 x보다 크면 숫자가 커지는 영향을 주는 end포인터를 줄여서 합의 범위를 줄여주는 것을 생각해 볼 수 있다. 

 

 만약 두 수의 합이 x보다 작은 경우를 생각해보자. x = 13인데 1 + 11 은 x보다 작다. 그렇다는 것은 start를 늘려서 11에 필요한 1이 아닌 큰 값을 찾아야 한다는 것을 의미한다. 숫자가 만약 더 작아진다면 1이 아닌 다른 수라고 해봤을 때 만족하지 않아 start를 줄이게 되면 더 작아지는 값을 가지기 때문에, 또 13에 가까워질 수 있는 방법이 없다. 조금 더 확실한 방법을 생각해 보기 위해 아래 예제를 보자.

 

해당 예제는 예제 입력 1에서 x값만 변경했다.

 

1 2 3 5 7 9 10 11 12, x = 14

 

그러면 위 예제에서 14를 찾기 위해서 start, end를 끝 포인터에 각가 두고 검사를 하게 된다.

하지만 1 + 12 = 13 이라서 x보다 작다 그렇다는 건 현재 가장 큰 값을 가리킴에도 불구하고, 1이 + 12와 더했을 때 = 14를 만족하는 값이 아니라는 것이다. 따라서 start를 올려 start가 2를 가리키게 되면 start = 2, end = 12가 되어 값을 만족하게 된다.

 

그럼 여기서 두 번째 아이디어가 사용 될 수 있다. x = 14니까 1.. 2.. 3. 같은 값들은 다른 수들에 대해서 특정 한 값을 오직 하나만 가지게 된다. 그러므로 2에 어울리는 값이 12가 되기 때문에, 두 수는 중 어느 한 수도 다른 수들과 더 했을때 x를 만족하는 값을 가지지 못한다. 이미 만족하는 다른 수를 찾았기 때문이다.

 

결국 두 수는 더 이상 서로 다른 어떤 값들을 만나도 x를 만족하지 않으므로 start, end를 각각 진행 방향 그대로 증가 감소 시킨다.

 

그러다가 5와 10을 만나는 순간이 온다. 이 순간에는 x보다 큰 값을 가지게 된다. x보다 큰 값을 가진다는 것은 end가 현재 start에 맞는 큰 값을 가지고 있지 않기 때문에 합의 범위를 줄이기 위해서 end를 줄여야 한다는 것을 의미한다. 만약 end를 줄이지 않고 start를 감소시키는 것은 투 포인터의 방향성이 반대가 된다는 것을 의미하며 이것은 투 포인터 알고리즘이 더 이상 아니게 된다. 또한 투 포인터 알고리즘이 아닌 이유가 아니더라도, 이미 start는 증가시키면서 값을 찾아왔기 때문에, 이전에 값을 찾았다면 해당 값은 더 이상 다른 값을 가질 수 없고, 이전에 값을 찾지 못했다면 그 수에 대해서 x를 만족시키는 값이 없다는 것을 의미한다.

 

이것은 배열이 정렬되어 있기 때문이며, 두 번째 생각에서

 

1 + 13 = 14

2 + 12 = 14

3 + 11 = 14

 

위와 같은 예시로 설명을 해볼 수 있는데 만약 1에 맞는 13이라는 값이 배열에 존재하지 않는다면 그 값이 지나 2를 가리키게 되어

12가 아닌 더 큰 값을 가지게 되었다고 가정해봤을때, 이전 1로 돌아간다고 하더라도 1에 해당하는 값이 큰 수에서 작은 수로 진행하기 때문에, start를 감소한다고 하더라도 값을 찾지 못하는 것이다. 다시 위 예제 5, 10을 바라봤을 때, 5가 아닌 start를 감소시켜 3.. 2.. 1로 진행한다고 해보면 3 + 10이라고 해도 = 13이고, 2 + 10 = 12가 되고, 1 + 10 = 11이 되면서, 값이 더 작아진다고 하더라도

이전에 start가 가리킨 값이 start 원소에 맞는 다른 원소를 찾지 못했다면, 이전 진행 방향으로 간다고 해서 값을 찾을 수 있는게 아니라는 것이다.

 

 

더 쉬운 예로 접근해 본다면, 아래는 5자리에 4로 변경한 예이다.

 

1 2 3 4 7 9 10 11 12, x = 14

 

start, end는 각각 끝 값부터 찾기 때문에 1..2..3.. 까지 전부 값을 만족하여 더 이상 각각의 수들은 다른 수들에 대해서 서로 만족하는 x를 찾을 수 없다. 그랬을 때 4가 위치한 위치에서 end는 10을 가리키기 때문에 start가 증가하는 방향 이전에 만약 4에 대해서 x를 만족하는 값을 찾지 못했다면 이후에도 찾을 수 없다는 것이다. 

 

결국 start, end는 두 수의 합이 x를 만족했을 때, 이미 각 수들은 두 수의 합을 만족하는 각각의 쌍을 이루었기 때문이고

그러므로 x보다 커져서, start를 줄인다고 하면 이전에 진행해 온 수들은 이미 값을 찾아서 사라졌거나, (사라졌으니 없다고 보면 되고)

그 수는 end가 가리키는 값보다 더 커야 한다.

 

 

 더 쉬운 예제로 일반화 시켜보려고 하다 보니 다소 난잡한 부분이 있을 수 있지만, 결론만 놓고 보면 이전에 start가 가리키는 값이 end가 가리키는 값에 대해서 x를 만족하지 않고, 만약 두 수의 합이 x보다 크다고 했을 때, start를 감소시킨다고 해서, 이전 값이 현재 end가 가리키는 값과의 합이 x를 만족할 수 없다는 내용이다. 왜냐하면 이전에 start가 가리키는 값은 end가 가리키는 값에 대해서 만족하거나, 만족하지 않다면 start, end가 이동했을 때 만족할 수 없으므로 그래서 값이 작거나 클 때, 합의 범위를 늘리거나 줄이게 된다는 것은 특정 값에 대해서, 만족하는 두 수를 찾겠다는 의미다. 

 

이해가 잘 가지 않는다면, 위에 1 + 13 = 14, 2 + 12 = 14, 3 + 11 = 14를 세로로 적어놓은 부분을 start, end 를 각각의 수로 두고 옮겨가면서 이해해 보면 이해가 더 쉬울 수도 있을 것 같다.

 

그래서 이 문제는 선형 시간으로 해결하게 되는 O(n)의 시간복잡도를 갖게 되는 알고리즘은 투 포인터로 해결할 수 있는 것이다.