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

숨·2025년 1월 11일

코테

알고리즘 문제 풀이

목록 보기

96/105

📌 문제 : 백준 2473번

📌 문제 탐색하기

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

문제 풀이

3가지 용액을 혼합해 특성값이 0에 가장 가까운 용액 3가지의 특성값을 출력하는 문제이다.

출력 조건은 다음과 같다.
1. 오름차순 출력
2. 0에 가장 가까운 용액 만들어내는 경우 2개 이상 → 아무거나 1개 출력

⭐️ 특성값 구하기

특성값

혼합에 사용된 각 용액의 특성값의 합

알칼리성 용액만 사용 또는 산성 용액만 사용 🆗

N의 범위가 $3 ≤ N ≤ 5,000$ 이고,
특성값의 범위가 $-1,000,000,000 ≤ value ≤ 1,000,000,000$ 로 매우 크다.

이 범위의 값을 하나하나 탐색한다면 시간 초과가 날 것이다.
따라서 시간복잡도를 효율적으로 줄일 수 있는 알고리즘이 필요하다.
→ 투 포인터(Two Pointer) 활용‼️

투 포인터 구현

먼저 용액 특성값들 오름차순 정렬
계산해서 비교할 합 → 큰 수로 정의
탐색 방식
- 특성값 리스트에 접근
- 1개의 용액을 먼저 선택해 나머지 2개의 용액 탐색한다고 가정
  - 각각의 인덱스 →left, right로 정의
  - 첫번째 용액 고정 & 그 다음 범위를 탐색
- 간격을 좁혀가며 합 계산하고 비교
  - 합의 절댓값이 저장한 합의 절댓값보다 작다 → 값 없데이트
  - 합 < 0 → left 값 증가 (더 큰 수로 이동)
  - 합 > 0 → right 값 감소 (더 작은 수로 이동)
종료 조건
- left가 right와 같거나 더 커질 경우

가능한 시간복잡도

오름차순 정렬 → $O(N log N)$
투 포인터 탐색 → $O(N * N) = O(N^2)$

최종 시간복잡도
$O(N^2)$ 가 된다.
최악의 경우 $O(5000^2)$ 이 되어 제한 시간 1초 내에 연산이 가능하다.

알고리즘 선택

투 포인터로 선택할 용액 범위 좁혀서 탐색

📌 코드 설계하기

N 입력
N개 용액 특성값 입력
오름차순 정렬
결과 저장 리스트 정의
합 큰 수로 정의
투 포인터 구현
6-1. 2개의 용액 지정
6-2. 투 포인터
6-2-1. 현재 합 계산
6-2-2. 합의 절댓값 비교해 더 작으면 저장
6-2-3. 탐색 범위 좁히기
결과 출력

📌 시도 회차 수정 사항

1회차

결과로 리턴할 리스트에 아무것도 저장되지 않았다.
비교할 0과 가장 가까운 경우의 값을 갱신해주는 코드를 빼먹었다.
합의 절댓값 비교해 더 작으면 저장한다고 했는데 정작 코드는 더 크면 저장한다고 잘못 작성해서 발생한 문제였다.

2회차

예제에 대해서 코드가 제대로 작동했는데 제출하니 틀렸습니다가 나왔다.
처음에 정의한 합의 값을 1000000000로 했었는데 이 값이 너무 적어서 발생한 문제였다. 5000000000으로 충분히 큰 수를 넣어서 해결했다.

📌 정답 코드

import sys

input = sys.stdin.readline

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

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

# 오름차순 정렬
values.sort()

# 결과 저장 리스트 정의
answer = []

# 합 큰 수로 정의
sum = 5000000000

# 투 포인터 구현
for i in range(N - 2):
    # 2개의 용액 지정
    left, right = i + 1, N - 1

    # 투 포인터 구현
    while left < right:
        # 현재 합 계산
        temp = values[i] + values[left] + values[right]

        # 합의 절댓값 비교해 더 작으면 저장
        if abs(temp) < sum:
            # 합 갱신
            sum = abs(temp)
            # 정답 갱신
            answer = [values[i], values[left], values[right]]

        # 탐색 범위 좁히기
        if temp < 0:    # 더 큰 수로 이동
            left += 1
        elif temp > 0:  # 더 작은 수로 이동
            right -= 1
        else:   # 가장 0에 가까운 경우로 바로 종료
            break

# 결과 출력
print(*answer)