[Problem Solving] 백준 2295 세 수의 합

세 수의 합 문제에 대한 자세한 설명은 다음의 링크를 참고해주시기 바랍니다. 문제 설명

2295번: 세 수의 합

정수 배열이 주어지면 적절하게 3개의 수를 선택하여 더한 결괏값이 정수 배열에 있는 정수 중에 가장 큰 수를 결과로 반환하는 문제입니다.

 

처음 문제에 대해서 접근할 때에는 조합과 이진 탐색을 사용하여 문제를 해결하려고 하였습니다. 하지만 조합의 시간 복잡도 O(n^3) 이진 탐색의 시간 복잡도 O(logn) 이므로 통합 시간 복잡도 O(n^3 logn)으로 n의 최댓값이 1,000인 것을 고려하였을 때 시간 초과가 나오게 됩니다.

 

따라서 target = a1 + a2 + a3 공식을 target - a3 = a1 + a2로 변환하여 접근하였습니다. 정수 배열의 2개 원소를 임의로 뽑아 더한 값을 set에 저장해준 다음에 다시 정수 배열에서 2개 원소를 임의로 뽑아 뺀 값이 앞의 집합에 존재하는지를 확인하는 방식입니다. a1 + a2를 더해서 set에 저장하는 연산 O(n^2) set에서 target 값이 존재하는지 확인하는 연산(해쉬 테이블) O(1)이므로 통합 시간 복잡도 O(n^2)로 문제를 해결할 수 있습니다.

 

해쉬 테이블이 아니라 이진 탐색을 사용해서 문제를 해결할 수도 있습니다. 앞의 방법의 set에서 target 값이 존재하는지 확인하는 연산만 이진 탐색 알고리즘으로 교체해주면 됩니다. 따라서 a1 + a2를 더해서 set에 저장하는 연산 O(n^2) set_list에서 target 값이 존재하는지 확인하는 연산(이진 탐색) O(logn)이므로 통합 시간 복잡도 O(n^2logn)로 문제를 해결할 수 있습니다.

 

다음은 이진 탐색과 해쉬 테이블을 사용한 문제 해결 코드입니다.

 

# 백준 No.2295 세 수의 합
import sys
input = sys.stdin.readline

def binary_search(target, array, left, right):
  if left > right:
    return False

  mid = (left + right) // 2

  if array[mid] == target:
    return True
  elif array[mid] > target:
    # target exist on the left
    return binary_search(target, array, left, mid - 1)
  else:
    # target exist on the right
    return binary_search(target, array, mid + 1, right)

n = int(input())
number_list = []

for _ in range(n):
  number_list.append(int(input()))

two_sum = set()
for x in range(n):
  for y in range(x, n, 1):
    two_sum.add(number_list[x] + number_list[y])

# 메모리 72344KB 시간 3840ms 이진탐색
answer = 0
two_sum_list = sorted(list(two_sum))
for x in range(n):
  for y in range(x, n, 1):
    target = abs(number_list[y] - number_list[x])
    if binary_search(target, two_sum_list, 0, len(two_sum_list) - 1):
      # answer exist on the target elements
      answer = max(answer, number_list[x] if number_list[x] > number_list[y] else number_list[y])
print(answer)

# 메모리 64656KB 시간 512ms 해쉬테이블
answer = 0
for x in range(n):
  for y in range(x, n, 1):
    target = abs(number_list[y] - number_list[x])
    if target in two_sum:
      # answer exist on the target elements
      answer = max(answer, number_list[x] if number_list[x] > number_list[y] else number_list[y])
print(answer)

 

처음 이진 탐색을 사용하여 문제를 해결하였을 때 문제가 없어보였는데 계속 "틀렸습니다"라는 결과가 나왔습니다. 탐색의 시간을 더 줄여야 한다고 생각하여 집합을 사용하여 target 값을 확인하는 방법으로 변경하였지만 결과는 같았습니다.

 

코드를 이리저리 바꾸다가 answer = max(answer, number_list[x] if number_list[x] > number_list[y] else number_list[y]) 줄에서 max 함수를 처리해주지 않고,  다음과 같이 처리해주었습니다. answer = number_list[x] if number_list[x] > number_list[y] else number_list[y] 최댓값만을 저장해야 하지만 조건만 맞다면 최댓값이 아니어도 answer의 값을 갱신하여 결과가 맞지 않았던 것 입니다.

 

시간을 많이 소비한 후라 허무하기도 하였지만 이진 탐색과 집합의 해쉬 테이블을 사용한 풀이에 대해서 모두 알 수 있어서 나쁘지만은 않았습니다.

 

알고리즘이나 프로젝트를 진행할 때에 이렇게 코드 몇 자 또는 조건 부등호 하나 때문에 프로그램이 제대로 실행되지 않는 경험들이 종종 보입니다. 이번 경우처럼 새로운 것을 얻는 다면 나쁘다고만 할 수는 없지만 종종 아무것도 얻는 게 없고 시간만 보내는 경우도 생기기 때문에 코드를 작성할 때에는 꼼꼼하게 작성하여 위와 같은 실수를 발생하지 않게 하는 것이 좋은 것 같습니다.