[백준/C++] #2473 세 용액 (Two Pointer)

문제

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

 

구상

세 용액을 혼합하여 특성값이 0에 가장 가까운 용액을 만들어야 하고, 이때의 세 용액을 출력해야 하는 문제였다. 

두 용액 일 때는 아래와 같이 두개의 포인터를 이용해서 풀었었다. 

https://persi0815.tistory.com/entry/%EB%B0%B1%EC%A4%80C-2467-%EC%9A%A9%EC%95%A1-Two-Pointer

 

세 용액이면 어떡할까? 고민을 해봤는데, 한 용액을 고정한 뒤 나머지 두 용액을 투 포인터로 찾는 방법이 떠올랐다. 

 

알고리즘

: two pointer

 

풀이 + 코드

용액 특성값들을 배열에 넣고 투포인터 사용을 위해 정렬을 했다. 그리고, 한 용액을 선택한 뒤, 나머지 두 용액을 결정하자. brute force로 풀면 O(N^3)이 걸리지만, 투 포인터를 사용하여 O(N^2)로 시간복잡도를 줄였다.

 

용액의 특성값의 최대가 1,000,000,000라서 최대합이 3,000,000,000이고, 최소합이 -3,000,000,000이다. 그래서 int 자료형의 범위를 넘어서기에 long long을 써야 했다. 

* int:  4 byte / -2,147,483,648 ~ 2,147,483,647

* long long: 8 byte / -9,223,372,036,854,775,808 ~  9,223,372,036,854,775,807(2^63)

#include<iostream>
#include<vector>
#include<algorithm>
#include <climits>
#define MAX 5001
#define INF 987654321
#define endl "\n"
using namespace std;
/*
2473 세 용액

산성 용액: 1부터 1,000,000,000 / 알칼리성 용액: -1부터 -1,000,000,000
용액 수는 3~5000
*/

int n; // 용액의 수
vector<long long> liquids;
vector<long long> result(3);

void solution() {
    long long ans = LLONG_MAX;

    for (int i = 0; i < n - 2; i++) {
        int left_idx = i + 1;
        int right_idx = n - 1;

        while (left_idx < right_idx) {
            long long sum = liquids[i] + liquids[left_idx] + liquids[right_idx];

            if (abs(sum) < abs(ans)) { // 절댓값으로 비교해야 0이랑 뭐가 더 가까운지 확인 할 수 있음
                ans = sum;
                result[0] = liquids[i];
                result[1] = liquids[left_idx];
                result[2] = liquids[right_idx];
            }

            if (sum < 0) { // 작으면 키우고
                left_idx++;
            }
            else { // 크면 줄인다
                right_idx--;
            }
        }
    }

    sort(result.begin(), result.end());
    cout << result[0] << " " << result[1] << " " << result[2] << endl;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    // 입력
    cin >> n;
    liquids.resize(n);

    for (int i = 0; i < n; ++i) {
        cin >> liquids[i];
    }
    sort(liquids.begin(), liquids.end()); // 오름차순으로 정렬

    // 로직
    solution();

    return 0;
}

 

요즘따라 느끼는 거지만, 작성자도 헷갈리지 않는, 이해하기 쉬운 코드가 짤 때도 좋은 코드인 것 같다.  

 

그리고, #include <climits>를 통해 LLONG_MAX을 사용할 수 있었다. 한계값을 사용할때 꽤나 유용한 것 같다. 

climits 헤더 파일은 각 데이터 타입의 한계를 나타내는 상수들을 제공한다. 

CHAR_BIT: char 타입의 비트 수
SCHAR_MIN: signed char의 최소값
SCHAR_MAX: signed char의 최대값
UCHAR_MAX: unsigned char의 최대값
CHAR_MIN: char의 최소값 (컴파일러에 따라 signed 또는 unsigned)
CHAR_MAX: char의 최대값 (컴파일러에 따라 signed 또는 unsigned)
MB_LEN_MAX: 멀티바이트 문자 최대 크기

SHRT_MIN: short 타입의 최소값
SHRT_MAX: short 타입의 최대값
USHRT_MAX: unsigned short 타입의 최대값

INT_MIN: int 타입의 최소값
INT_MAX: int 타입의 최대값
UINT_MAX: unsigned int 타입의 최대값

LONG_MIN: long 타입의 최소값
LONG_MAX: long 타입의 최대값
ULONG_MAX: unsigned long 타입의 최대값
LLONG_MIN: long long 타입의 최소값
LLONG_MAX: long long 타입의 최대값
ULLONG_MAX: unsigned long long 타입의 최대값

이 상수들은 각각의 데이터 타입이 가질 수 있는 최소값과 최대값을 나타내며, 시스템 또는 컴파일러에 따라 다를 수 있다.