[파이썬/Python] 백준 2467번: 용액

숨·2024년 9월 24일

코테

알고리즘 문제 풀이

목록 보기

84/105

📌 문제 : 백준 2467번

📌 문제 탐색하기

N : 전체 용액의 수 $(2 ≤ N ≤ 100,000)$
values : N개 용액의 특성값 $(-1,000,000,000 ≤ value ≤ 1,000,000,000)$

N개 용액들의 특성값이 정렬된 상태로 입력되었을 때, 서로 다른 2개를 혼합해 특성값이 0에 가장 가까운 용액을 만드는 경우를 찾는 문제이다.

문제 풀이

처음에 N개 중 2개를 선택해 합을 계산하면서 0에 가까운 값을 찾으면 될 것이라 생각했다.
시간 복잡도가 $O(N^2)$ 이 되는데 N의 값이 매우 크기 때문에 1초 내 연산이 되지 않을 것 같았다.

이런 경우 시간 복잡도를 $O(N)$ 까지 줄일 수 있는 투 포인터를 사용하면 된다.

🤖 투 포인터 (Two Pointers)

리스트에 순차적 접근 시, 2개의 점 위치 기록하며 처리하는 알고리즘

구현 방법

시작 인덱스, 종료 인덱스 지정

투 포인터 이동 원칙 활용해 배열 끝까지 탐색

시작 인덱스 오른쪽 한 칸 이동 = 연속된 자연수의 왼쪽 값 삭제

종료 인덱스 오른쪽 한칸 이동 = 연속된 자연수 범위 한 칸 확장

이 문제를 투 포인터로 해결하기 위해 먼저 시작 인덱스, 종료 인덱스를 지정한다.
→ 시작 인덱스 = 0, 종료 인덱스 = N-1(특성값의 마지막)

찾고자 하는 값은 합했을 때 0과 가까운 값이다.
이미 특성값은 정렬된 상태이므로 인덱스를 옮길 때마다 합을 계산해 0과 가까운지 확인한다.

→ 특성값이 음수도 있기 때문에 합에 절댓값을 취해 갱신한다.

합이 0이라면?
- 바로 반복 종료 후 정답 출력
합이 0보다 크다면?
- 오른쪽 포인터 왼쪽 이동 → 더 작은 합 만들기
합이 0보다 작다면?
- 왼쪽 포인터 오른쪽 이동 → 더 큰 합 만들기
매번 0과 가까운 값 갱신 → 두 포인터 교차할 때까지 반복

가능한 시간복잡도

길이 N인 특성값 리스트에서 투 포인터 수행 → $O(N)$

최종 시간복잡도
$O(N)$ 이 되어 최악의 경우 $O(100,000)$ 으로 1초 내 연산 가능하다.

알고리즘 선택

투 포인터로 원하는 결과 찾기

📌 코드 설계하기

필요한 입력받기
시작, 종료 인덱스 지정
정답 저장 변수 초기화
투 포인터 진행
결과 출력

📌 시도 회차 수정 사항

1회차

예제들은 원하는대로 동작했으나 틀렸습니다 결과를 얻었다.
반복문 내에서 조건에 따라 포인터를 옮길 때 0과 비교하는 값을 0과 가장 가까운 값들의 합을 의미하는 answer_sum으로 했다.
포인터 이동 방향은 현재 인덱스들의 합으로 결정해야 했는데 갱신하는 값으로 결정했다. 이 부분을 수정해 해결했다.

📌 정답 코드

import sys

input = sys.stdin.readline

# N 입력
N = int(input())

# 특성값 입력
values = list(map(int, input().split()))

# 시작, 종료 인덱스 지정
start, end = 0, N - 1

# 0과 가까운 값의 합을 저장할 변수 초기화
answer_sum = 2000000000
answer_pair = [0, 0]

# 포인터 겹칠 때까지 반복
while start < end:
    # 합 구하기
    temp_sum = values[start] + values[end]

    # 절댓값이 0과 가까운지 확인 후 갱신
    if abs(answer_sum) > abs(temp_sum):
        answer_sum = temp_sum
        answer_pair = [values[start], values[end]]

    # 합이 0이면 반환
    if temp_sum == 0:
        break

    # 합이 0보다 크면 오른쪽 포인터 왼쪽 이동
    if temp_sum > 0:
        end -= 1
    # 합이 0보다 작다면 왼쪽 포인터 오른쪽 이동
    else:
        start += 1

# 정답 출력
print(' '.join(map(str, answer_pair)))