TIL) 2470 두 용액

이 글은,
1. 미래의 내가 다시 이 문제를 풀고자 할 때 과거의 내가 어떻게 문제를 해결했었는지 알려주기 위해서
2. 같은 문제를 풀고 있는 사람에게 아이디어를 제공하기 위해서
작성되었습니다.

👽 두 용액

백준 2470 두 용액 : https://www.acmicpc.net/problem/2470

데이터의 크기를 보고 이진탐색으로 접근했다.
(-1,000,000,000 이상 1,000,000,000 이하)
하지만 다시 문제를 푼다면 투포인터로 접근하는게 더 쉬운 방법일 것 같다.

👩‍🏫 내가 푼 풀이 - 시간초과

def recur(array, start, end, num1):
    global answer
    # 종료 조건
    if start >= end:
        answer.append([num1, array[end]])
        # print("여기는 start > end : "+str(num1)+ " "+str(array[end]))
        return
    mid = (start + end)//2
    if array[mid] + num1 == 0:
        # print(f'여기는 총합이 0 : {num1} {array[mid]}')
        answer.append([num1, array[mid]])

    if array[mid] + num1 < 0:
        recur(array, mid+1, end, num1)
    elif array[mid] + num1 > 0:
        recur(array, start, mid-1, num1)



# main함수
N = int(input())
array = list(map(int, input().split()))
array.sort()
answer = []
result = []

# 음수만 있는 경우
if array[-1] <= 0:
    result = [array[-1], array[-2]]
    # print(f'{array[-1]} {array[-2]}')

# 양수만 있는 경우
elif array[0] >= 0:
    result = [array[0], array[1]]
else:
    for num1 in array:
        array.remove(num1)
        recur(array, 0, N-2, num1)
# print(answer)


abs_num = 2e9
for i in range(len(answer)):
    temp = abs(answer[i][0] + answer[i][1])
    if abs(temp) < abs_num:
        abs_num = temp
        result = [answer[i][0], answer[i][1]]
print(result)

정확히 어느 부분에서 시간초과가 발생하는지 모르겠다 😥

먼저 용액이 모두 음수인 경우, 양수인 경우를 걸러주고
섞여 있는 경우에만 recur() 함수를 호출해서 num1과 더했을 때 0에 가장 가까운 수를 answer에 넣어준다. (비교하는 부분에서 시간초과가 발생했을까?)

이렇게 풀면 답은 나오지만 시간초과가 발생한다.

👪 팀원들과 함께 푼 풀이 - 통과

import sys
# sys.stdin = open("./백준 문제 파일/week02/baekjoon/two-sol.txt", "r")

sol_num = int(input())
solutions = sorted(map(int, input().split()))

def find_value(solution, origin, target):
  pl = 0
  pr = len(solution)-1
  while True:
    pc = (pl + pr) // 2
    if solution[pc] == target:
      return [origin, solution[pc]]
    elif target < solution[pc]:
      pr = pc -1
    else:
      pl = pc + 1
    if pr < pl:
      if pr >= 0 and pl < len(solution):
        if solution[pl] - target <  target - solution[pr]:
          return [origin, solution[pl]]
        else:
          return [origin, solution[pr]]
      elif pr < 0:
        return [origin, solution[pl]]
      else:
        return [origin, solution[pr]]

temp_list = list()
if solutions[0] >= 0:
  print(f"{solutions[0]} {solutions[1]}")
elif solutions[-1] <= 0:
  print(f"{solutions[-2]} {solutions[-1]}")
else:
    for solution in solutions:
        temp_list.append(find_value(solutions, solution, -solution))

    new_temp_list = []
    for temp in temp_list:
        if temp[0] - temp[1] != 0:
            new_temp_list.append([abs(sum(temp)), temp])
	
    # 짝꿍 숫자의 순서가 뒤집혀 있을 경우 정렬해주기
    finally_want = sorted(new_temp_list)[0]
    # print(finally_want)
    if finally_want[1][0] > finally_want[1][1]:
        finally_want[1][0], finally_want[1][1] = finally_want[1][1], finally_want[1][0]

    print(*finally_want[1])

팀원들과 함께 풀었을 때에는 find_value() 함수에 target이라는 값을 미리 구해서 넣어주었다. 그리고 원래 숫자와 target으로 구한 숫자를 리스트로 묶어 리턴해주었다.

계속 시간초과, 반례 발견이 반복되다가 4시간만에 통과했다. 끝까지 포기하지 않은 팀원들 정말 최고다👍👍👍