[Code Up] 4701번 : 두 용액

난이도  ⭐️ ⭐️ ⭐️ ⭐️ ⭐️  (최상)

문제 설명

두 용액

KOI 부설 과학연구소에서는 많은 종류의 산성 용액과 알칼리성 용액을 보유하고 있다. 각 용액에는 그 용액의 특성을 나타내는 하나의 정수가 주어져있다.  산성 용액의 특성값은 1부터 1,000,000,000까지의 양의 정수로 나타내고, 알칼리성 용액의 특성값은 -1부터 -1,000,000,000까지의 음의 정수로 나타낸다.

 

같은 양의 두 용액을 혼합한 용액의 특성값은 혼합에 사용된 각 용액의 특성값의 합으로 정의한다. 이 연구소에서는 같은 양의 두 용액을 혼합하여 특성값이 0에 가장 가까운 용액을 만들려고 한다. 

 

예를 들어, 주어진 용액들의 특성값이 [-2, 4, -99, -1, 98]인 경우에는 특성값이 -99인 용액과 특성값이 98인 용액을 혼합하면 특성값이 -1인 용액을 만들 수 있고, 이 용액이 특성값이 0에 가장 가까운 용액이다. 참고로, 두 종류의 알칼리성 용액만으로나 혹은 두 종류의 산성 용액만으로 특성값이 0에 가장 가까운 혼합 용액을 만드는 경우도 존재할 수 있다.

 

산성 용액과 알칼리성 용액의 특성값이 주어졌을 때, 이 중 두 개의 서로 다른 용액을 혼합하여 특성값이 0에 가장 가까운 용액을 만들어내는 두 용액을 찾는 프로그램을 작성하시오.

입출력

[ 입력 ]

첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,000,000 이하이다. N개의 용액들의 특성값은 모두 다르고, 산성 용액만으로나 알칼리성 용액만으로 입력이 주어지는 경우도 있을 수 있다.

[ 출력 ]

첫째 줄에 특성값이 0에 가장 가까운 용액을 만들어내는 두 용액의 특성값을 출력한다. 출력해야 하는 두 용액은 특성값의 오름차순으로 출력한다. 특성값이 0에 가장 가까운 용액을 만들어내는 경우가 두 개 이상일 경우에는 그중 아무것이나 하나를 출력한다.

예시

[ 입력 예시 ]

5 -2 4 -99 - 98

[ 출력 예시 ]

-99 98

문제풀이

문제 풀이에 앞서 아래의 해당 문제를 다룬 포스팅을 참조하여 필자가 풀고자하는 C언어로 프로그래밍하였다.

백준 2470 두 용액

과정 (1) : 퀵 정렬은 써야 문제가 풀리지만 어디서 써야하는가  

아래의 [더보기]의 코드는 필자가 처음 작성한 코드이다.

해당 코드를 살펴보면, 입력받은 배열을 반복을 통하여 계산한 값을 동적할당한 배열에 일일이 저장한다. 이때 반복 횟수는 nC2로 5개를 받으면 10번 조건을 확인한다.

 

따라서 동적할당한 배열을 nC2로 할당하여 선언했다.

하지만 이러한 코드는 눈으로 보기에 어떠한 값이 가장 0에 가까운지만 볼 수 있을 뿐, 문제가 원하는 답이 아님을 깨닫고 다른 방법을 시도했다.

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
void quickSort(int arr[], int L, int R){
    int left = L, right = R,tmp;
    int Piv = arr[(L+R)/2];
    do{
        while(arr[left] < Piv) left++;
        //left가 Piv보다 큰 값을 만나거나 피벗(Piv)을 만날때 까지
        while(arr[right] > Piv) right--;
        //right Piv보다 작은 값을 만나거나 피벗(Piv)을 만날때 까지
        if( left <= right){
            tmp = arr[left];
            arr[left]= arr[right];
            arr[right] = tmp;

            left++; right --;
        }
    } while(left <= right);

    if(L < right) quickSort(arr,L,right);
    if(R > left) quickSort(arr,left,R);
}

int main(){
    int num[10001],N,cnt=0;
    scanf("%d",&N);
    int *rst = (int*)malloc((N*(N-1)/2)*sizeof(int));

    for(int i=0;i<N;i++)scanf("%d",&num[i]);
    for(int i=0;i<N;i++){
        for(int j=i+1;j<N;j++){
            rst[cnt] = num[i] + num[j];
            cnt ++;
        }
    }
    // for(int i=0;i<10;i++)rst[i] = i +1;
    for(int i=0;i<(N*(N-1)/2);i++)printf("%d ",rst[i]);
    
    quickSort(rst,0,(N*(N-1)/2)-1);printf("\n");
    for(int i=0;i<(N*(N-1)/2);i++)printf("%d ",rst[i]);
} 
/*

*/

과정 (2) : 계산한 결괏값을 음수와 양수의 배열에 각각 저장하여 구별하자. 

아래의 [더보기]의 코드는 필자가 두 번째로 작성한 코드이다.

과정(1)의 코드를 재활용하여 두 개의 결과 배열로 도출하였고, 음수 결괏값의 마지막 요소와 양수 결괏값의 가장 첫 번째 요소를 비교하여 가장 특성값이 작은 결괏값을 찾는 알고리즘이다.

 

이는 과정(1)에서 특성값을 찾을 수 있는 알고리즘을 더한 코드이지만, 문제가 원하는 답을 찾을 수 없어 다른 방법을 시도했다.

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
void quickSort(int arr[], int L, int R){
    int left = L, right = R,tmp;
    int Piv = arr[(L+R)/2];
    do{
        while(arr[left] < Piv) left++;
        //left가 Piv보다 큰 값을 만나거나 피벗(Piv)을 만날때 까지
        while(arr[right] > Piv) right--;
        //right Piv보다 작은 값을 만나거나 피벗(Piv)을 만날때 까지
        if( left <= right){
            tmp = arr[left];
            arr[left]= arr[right];
            arr[right] = tmp;

            left++; right --;
        }
    } while(left <= right);

    if(L < right) quickSort(arr,L,right);
    if(R > left) quickSort(arr,left,R);
}

int main(){
    int num[10001],N,pos_cnt=0,neg_cnt=0;
    scanf("%d",&N);
    int *pos = (int*)malloc((N*(N-1)/4+1)*sizeof(int));
    int *neg = (int*)malloc((N*(N-1)/4+1)*sizeof(int));

    for(int i=0;i<N;i++)scanf("%d",&num[i]);
    for(int i=0;i<N;i++){
        for(int j=i+1;j<N;j++){
            int rst = num[i] + num[j];
            if(rst < 0) {neg[neg_cnt] = rst;neg_cnt++;}
            if(rst >= 0) {pos[pos_cnt] = rst;pos_cnt++;}
        }
    }

    
    quickSort(neg,0,neg_cnt-1);//printf("\n");
    quickSort(pos,0,pos_cnt-1);
    // for(int i=0;i<neg_cnt;i++)printf("%d ",neg[i]);
    // printf("\n");
    // for(int i=0;i<pos_cnt;i++)printf("%d ",pos[i]);
    int val = abs(neg[neg_cnt-1])<abs(pos[0])?neg[neg_cnt-1]:pos[0];
    printf("%d",val);
    // for(int i=0;i<(N*(N-1)/2);i++)printf("%d ",rst[i]);
} 
/*

*/

과정 (3) : 절대값이 가장 작은 수가 특성값이다!

아래의 [더보기]의 코드는 필자가 세 번째로 작성한 코드이다.

해당 코드부터는 절대값을절댓값을 떠올리고 절댓값을 이용한 코드를 작성했다. 특성값은 0에 가까워야 하므로 절댓값이 0에 가깝거나 0이면 정답이라는 생각이 들어 코드를 작성했다.

 

하지만 해당 코드에서 처음으로 런타임 오류와 시간 초과가 발생했고, N의 값이 횟수가 늘어날 수록 반복의 횟수가 기하급수적으로 증가한다는 사실을 깨달았다. 과정(1)에서 언급했던 nC2의 반복 횟수가 N이 증가함에 따라 시간 초과로 이어진다는 것을 이해하고 반복을 사용하지 않고 해당 문제를 푸는 방법에 대해 고민하기 시작했다.

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
int main(){
    int num[100001],N,cnt=0,min;
    scanf("%d",&N);
    int *rst = (int*)malloc((N*(N-1)/2)*sizeof(int));

    int idx[2],val;

    for(int i=0;i<N;i++)scanf("%d",&num[i]);

    for(int i=0;i<N;i++){
        for(int j=i+1;j<N;j++){
            rst[cnt] = num[i] + num[j];

            if(cnt==0)min = rst[0];

            if(min>abs(rst[cnt])){
                val = rst[cnt];
                min= abs(rst[cnt]);
                idx[0] = num[i];
                idx[1] = num[j];
            }
            cnt ++;
        }
    }
    // for(int i=0;i<10;i++)rst[i] = i +1;
    // for(int i=0;i<(N*(N-1)/2);i++)printf("%d ",rst[i]);
    // printf("\nval = %d | %d + %d",val,idx[0],idx[1]);
    printf("\n");
    printf("%d %d",idx[0],idx[1]);

    
} 
/*
-1  2
*/

과정 (4) : 굳이 이중 반복을 할 이유가 없네?

시간초과를 해결하기 위해서 열심히 구글링을 했으나 C언어로 된 문제 풀이를 발견할 수 없었다. 내가 앞서 푼 알고리즘 또한 틀린 알고리즘은 아니나 많은 시간이 걸린다는 단점을 이해했고, 해당 문제점을 해결하기 위에서 자료를 찾다가 본문 처음에 언급한 블로그를 보게 되었다.

 

이 문제 풀이의 핵심은 바로 '절대값 기준 정렬'이었다.

 

예를 들어 입력에 예시를 이용해 보자.

2 4 -99 -1 98과 같은 수를 절댓값 기준 정렬을 한다면 -1(A) 2(B) 4(C) 98(D) -99(E)이다.

 

절댓값 정렬을 하지 않는다면, B와 D의 합이 B와 C의 합 혹은 C와 D의 합보다 절댓값이 더 작다

 

이때 B C D는 아래의 항목을 만족한다.

 

1. B C D 순서대로 음수, 음수, 음수 or 양수, 양수, 양수와 같이 세 수 모두 부호가 같을 경우

2. B와 D가 다른 부호일 경우(음양양, 음음양, 양양음, 양음음)
3. B와 D가 같은 부호인데 C만 다를 경우(양음양, 음양음)

 

1) 번의 경우 절댓값의 합이 커진다.

3) 번의 경우,

음수와 음수를 더하거나 양수와 양수를 더하면 절댓값이 더 커지는데, 중간에 있는 부호가 다른 수를 더하면 절대값이 작아진다.

 

2) 번의 경우,

부호가 다른 숫자는 부호가 같은 두 개의 숫자 중 자기와 거리가 더 가까운 것과 합하여야 한다.

 

2.1. 음양양의 경우 : B와 C의 합이 B와 D의 합보다 절댓값이 더 작다
2.2. 음음양의 경우 : C와 D의 합이 B와 D의 합보다 절대값이 더 작다
2.3. 양양음의 경우 : C와 D의 합이 B와 D의 합보다 절대값이 더 작다
2.4. 양음음의 경우 : B와 C의 합이 B와 D의 합보다 절대값이 더 작다

따라서 절댓값으로 정렬하여 이웃한 수끼리만 보면 된다.

정답코드

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>

void quickSort(int arr[], int L, int R){
    int left = L, right = R,tmp;
    int Piv = abs(arr[(L+R)/2]);
    do{
        while(abs(arr[left]) < Piv) left++;
        //left가 Piv보다 큰 값을 만나거나 피벗(Piv)을 만날때 까지
        while(abs(arr[right]) > Piv) right--;
        //right Piv보다 작은 값을 만나거나 피벗(Piv)을 만날때 까지
        if( left <= right){
            tmp = arr[left];
            arr[left]= arr[right];
            arr[right] = tmp;

            left++; right --;
        }
    } while(left <= right);

    if(L < right) quickSort(arr,L,right);
    if(R > left) quickSort(arr,left,R);
}

int main(){
    int num[100001],N,rst[2];
    scanf("%d",&N);
    for(int i=0;i<N;i++)scanf("%d",&num[i]);
    
    quickSort(num,0,N-1);

    int val;
    for(int i=0;i<N-1;i++){
        if(i==0){
            val = abs(num[0] + num[1]);
            rst[0] = num[i]; 
            rst[1] = num[i+1];
        }
        else if(val > abs(num[i]+num[i+1])){
            val = abs(num[i]+num[i+1]);
            
            rst[0] = num[i]; 
            rst[1] = num[i+1];
        }
    }
    // for(int i=0;i<N;i++)printf("%d ",num[i]);
    if(rst[0] > rst[1]){
        int tmp = rst[0];
        rst[0] = rst[1]; rst[1] = tmp;
    }
    printf("%d %d",rst[0],rst[1]);
} 
/*

*/