[Baekjoon] 2473. 세 용액 [G4]
📚 문제
https://www.acmicpc.net/problem/2473
📖 풀이
n은 5000개 이하로 주어져 있다. 5000개 중 하나를 고르고, 나머지 2개는 투포인터를 활용하여 구한다.
투포인터를 활용하기 위해 정렬한다.
하나를 고른 후 s는 0 e는 n-1로 둔다.
골랐던 값이 s와 같으면 s를 1 늘리고, e랑 같으면 e를 1 줄인다.
세 수의 합이 0보다 크면 e를 1 줄인다.
세 수의 합이 0보다 작으면 s를 1 늘린다.
세 수의 합이 0이 나오면 바로 그 세 수를 출력하고 종료한다.
📒 코드
n = int(input())
arr = sorted(list(map(int, input().split())))
result = abs(arr[0] + arr[1] + arr[2]) # 비교하기 위한 값, 배열 앞에서 3개 선택하여 더한 후 절댓값을 넣는다.
result_arr = [arr[0], arr[1], arr[2]] # 배열에 세 수를 담아준다.
for i in range(n): # 하나를 우선 선택한다.
a = arr[i] # 하나 선택
s = 0 # 투포인터
e = n - 1
while s < e: # 같지 않을 때만 봐야 한다.
if s == i: # 선택한 값을 중복 선택하지 않기 위함
s += 1
continue
if e == i:
e -= 1
continue
if abs(a + arr[s] + arr[e]) < result: # 이전에 구한 값보다 작은 경우만
result = abs(a + arr[s] + arr[e]) # 세 수의 합의 절댓값을 초기화
result_arr = [a, arr[s], arr[e]] # 출력해야하니 배열에 담는다.
if a + arr[s] + arr[e] == 0:
print(*sorted([a, arr[s], arr[e]])) # 합이 0이면 바로 출력한다.
exit()
elif a + arr[s] + arr[e] > 0: # 합이 0보다 큰 경우 큰 값을 줄인다.
e -= 1
else: # 합이 0보다 작으면 작은 값을 키운다.
s += 1
print(*sorted(result_arr)) # 세 수를 정렬해 작은 수부터 출력한다.
🔍 결과
Author And Source
이 문제에 관하여([Baekjoon] 2473. 세 용액 [G4]), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@yunhlim/Baekjoon-2473.-세-용액-G4저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)