[BOJ] 백준 7453번 : 합이 0인 네 정수 (JAVA)

문제

정수로 이루어진 크기가 같은 배열 A, B, C, D가 있다.

 

A[a], B[b], C[c], D[d]의 합이 0인 (a, b, c, d) 쌍의 개수를 구하는 프로그램을 작성하시오.

 

 

입력

첫째 줄에 배열의 크기 n (1 ≤ n ≤ 4000)이 주어진다. 다음 n개 줄에는 A, B, C, D에 포함되는 정수가 공백으로 구분되어져서 주어진다. 배열에 들어있는 정수의 절댓값은 최대 228이다.

 

 

출력

합이 0이 되는 쌍의 개수를 출력한다.

 

 

풀이

Upper Bound와 Lower Bound를 이용하여 풀 수 있는 문제였습니다. 이 두 개념에 대해 모르시는 분은 이곳을 참고하여 이론을 이해하시고 소스코드가 어떻게 설계되는지 참고하시길 바랍니다.

 

사실 저는 처음에 Bound가 아닌 해쉬맵을 사용하였는데, 재채점 대란이 일어나고나니 이 코드가 시간초과가 떴습니다. 이 이유와 관련해서는 따로 아래에서 다루겠습니다.

 

 

Upper Bound는 find보다 큰 첫 번째 원소의 위치를 반환하고, Lower Bound는 find보다 크거나 같은 첫 번째 원소의 위치를 반환합니다.

 

예를 들어, arr = {1, 2, 2, 2, 3}이고, find = 2라고 해 봅시다. 그렇다면, Upper Bound는 4를 반환하고, Lower Bound는 1을 반환합니다.

 

 

Upper Bound나 Lower Bound는 대충 이해가 가실텐데, 이것을 왜 쓸까요? 사실, 우리는 이 문제에서 시간제한이 없다면 4중 반복문을 돌리면 됩니다. 하지만 그렇다면, 시간초과가 발생하기때문에 시간을 줄여야합니다.

 

2중 반복문을 돌리면서 A와 B의 합을 구한 배열(AB)과 C와 D의 합을 구한 배열(CD)를 따로 구합니다. 그리고 AB의 요소를 하나씩 순회하면서 -(AB의 요소)인 값이 CD에 존재하는지 확인하면 됩니다. 이 과정에서 HashMap의 containsKey()를 사용하면 될 것 같지만, 아쉽게도 이 문제에서는 통하지 않으므로 Upper Bound와 Lower Bound를 사용해야합니다.

 

AB와 CD의 요소를 더해서 합을 0으로 만들어야 하는데, -(AB의 요소)가 CD에 몇 개나 존재하는지 매번 확인하면 됩니다. 이때, 단순히 이진탐색만 사용하면 여러 개의 값을 못 찾기때문에 Upper Bound와 Lower Bound를 사용하는 것입니다.

 

가령, -(AB의 요소)가 2이고, CD에는 {1, 2, 2, 2, 3}가 있다고 합시다. 일반 이진탐색을 사용한다면, CD에서 2를 하나만 찾고 탐색이 끝날 것입니다. 하지만, Upper Bound를 통해 3의 위치를 파악하고, Lower Bound를 사용하여, 처음 나오는 2의 위치를 파악한다면, 이 둘의 위치를 뺌으로써 2가 3개 있다는 사실을 알아낼 수 있습니다.

 

 

아래는 위 과정을 정리한 소스코드입니다.

 

 

소스코드

 

 

Upper Bound, Lower Bound 설계할 때 주의할 점

우리는 보통 이진탐색 소스코드를 구현할 때, right = arr.length - 1로 하고 while문의 조건식으로 left <= right를 설정하는 경우가 많습니다. 하지만, Upper Bound나 Lower Bound를 구현할 때는 right = arr.length, while문의 조건식으로는 left < right로 설정해야 합니다. 그 이유는 right = mid + 1이 아니라 right = mid로 정의하기 때문입니다.

 

예를 들어, arr = {3}이고, find = 1이라고 해 봅시다. right = arr.length - 1이라면, left와 right는 0일 것입니다. 처음에, mid는 (0 + 0) / 2를 통해 0이 되고, arr[0] = 3으로 find보다 큽니다. 따라서 right = mid가 됩니다. 하지만, 눈치채셨듯이 right는 항상 0으로 초기화돼서 무한루프가 실행됩니다.

 

따라서, Upper Bound와 Lower Bound를 구현하실 때는 꼭 right를 열린 구간으로 정의해 주셔야합니다.

 

 

HashMap으로 풀면 안 되는 이유

저는 처음에 Upper Bound와 Lower Bound를 구현하기 귀찮아서 HashMap으로 CD의 요소를 저장한다음, containsKey()을 사용하여 풀었습니다. 그리고 put()과 containsKey() 모두 시간복잡도가 O(1)이라서 무조건 된다고 생각하였죠.

 

하지만, 해시 충돌이란 것이 발생하면 HashMap의 시간복잡도가 O(N)까지 올라간다는 사실을 알게 되었습니다. 여기서, 해시 충돌은 해시 함수가 서로 다른 두 개의 입력값에 대해 동일한 출력값을 내는 상황을 의미합니다. 이 질문글의 답변에 따르면, 값을 넣을 때마다 해시 충돌을 일으켜서 HashMap의 시간복잡도를 O(1)에서 O(N)까지 올려버릴수도 있다고 합니다.

 

많은 데이터를 HashMap에 저장해야할 경우 해시 충돌을 꼭 주의해야겠습니다.

 

 

지적 혹은 조언 환영합니다! 언제든지 댓글로 남겨주세요.