[BOJ] 2467. 용액

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

2467번: 용액

 

 

1. 해결방법

"""
1. 아이디어
- 입력받은 배열을 먼저 정렬한다.
- 투포인터를 활용 (맨 왼쪽, 맨 오른쪽)
- 두 개의 합을 구해서 abs(min_v)에 저장
- 합이 양수면 맨 오른쪽 인덱스 위치 -1, 음수면 맨 왼쪽 인덱스 위치 + 1
- 앞 서 저장한 min_v와 위치 이동한 인덱스 값의 합을 절댓값으로 비교
- 절댓값이 가장 작은 인덱스 값을 출력

2. 시간복잡도
- O(N)
"""

 

2. 정답코드

import sys
input = sys.stdin.readline

N = int(input())
nums = sorted(list(map(int, input().split())))

min_v = 0
left, right = 0, N - 1
left_v, right_v = 0, 0
answer_left, answer_right =0, 0
min_v = sys.maxsize

while left < right:
    left_v, right_v = nums[left], nums[right]
    add_v = left_v + right_v

    if abs(add_v) < min_v:
        answer_left, answer_right = left_v, right_v
        min_v = abs(add_v)

    if add_v > 0:
        right -= 1
        continue
    elif add_v < 0:
        left += 1
        continue
    else:
        break

print(answer_left, answer_right)

투포인터의 실버 레벨정도의 문제를 몇 문제 풀고 오면 쉽게 풀수 있는 문제이다. 난이도는 골드지만 체감상 골드는 아닌 느낌?
아무튼 시간복잡도를 고려해서 투포인터를 활용해야한다는 아이디어만 생각해내면 풀기에는 적당한 문제이지 않나 싶다. 좋은문제!