[백준 / C++] 2467번 용액

문제 재정의 및 추상화

결론: 수열에서 합이 0과 가장 가까운 두 수를 찾아라.

문제 접근 방식

음수와 양수가 존재할 수 있는 정렬된 수열에서 합을 구하므로 양쪽 끝에서부터 합을 구해본다.

해법을 찾는데 결정적이었던 깨달음

📌 같은 경우가 두 개 이상일 경우 그 중 아무것이나 하나를 출력한다고 했다.

즉, 양쪽 끝에서부터 탐색하다가 0이 되는 순간에는 바로 값을 확정해도 된다!

문제 풀이 로직

1. 전체 용액의 수 n을 입력받고, 용액 배열에 n개의 수를 입력받는다.
2. 왼쪽 끝 인덱스가 오른쪽 끝 인덱스보다 작을 동안 아래 모든 과정을 반복한다.
   2-1. 왼쪽 끝 숫자와 오른쪽 끝 숫자의 합 value를 저장해둔다.
   2-2. value의 절댓값이 최솟값보다 작으면 value의 절댓값을 최솟값으로 하고, 현재의 왼쪽 끝 숫자와 오른쪽 끝 숫자를 각각 최소 숫자로 저장한다.
   2-3. value 값이 0보다 크면 숫자를 작게 하기 위해 오른쪽 끝 인덱스를 하나 줄인다.
   2-4. value 값이 0보다 작으면 숫자를 크게 하기 위해 왼쪽 끝 인덱스를 하나 늘린다.
   2-5. 둘 다 아니면 반복에서 빠져나온다.
3. 위 과정을 통해 구한 최종 최솟값을 출력한다.

문제 풀이

#include <bits/stdc++.h>
using namespace std;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    long long n;
    int solution[100001];
    
    cin >> n;
    for(int i = 0; i < n; i++) cin >> solution[i];
    
    long long left = 0;
    long long right = n - 1;
    
    int min = abs(solution[left] + solution[right]);
	int minL = solution[left];
	int minR = solution[right];
    
    while(left < right){   
        int value = solution[left] + solution[right];
        
        if (abs(value) < min) {
			min = abs(value);
			minL = solution[left];
			minR = solution[right];
		}
		
        if(value > 0) right--; 
        else if (value < 0) left++;
        else break;
    }

    cout << minL << " " << minR;
    
    return 0;
}