[백준] 2467 용액 이분탐색

문제 :

www.acmicpc.net/problem/2467

2467번: 용액

분석 : 

이 방식은 시간 초과가 났다. 산성과 알칼리 용액을 구분해 배열에 담았고 각 배열이 끝날때까지 O(n^2)으로 탐색하는 방법을 사용했는데 가장 비효율적으로 문제를 푼거 같다. 그리고 딱히 map 함수를 사용하지 않아도 되었는데 쓸데 없는 악세사리가 많은 느낌 .. 

<두용액> 문제에서 더 효율적인 방법을 찾아 해결하였다. 

C++ 코드 :

//
//  2467_solution.cpp
//  SOMA👩🏻‍💻
//
//  Created by JoSoJeong on 2021/02/05.
//

#include <stdio.h>
#include <iostream>
#include <unordered_map>
#include <math.h>
#include <string>

using namespace std;

unordered_map<string, int> solution(int arr[],int n){
    int acidArr[n];
    int alkaliArr[n];
    fill_n(acidArr, n, -1);
    fill_n(alkaliArr, n, -1);
    
    int acidCount = 0;
    int alkaliCount = 0;
    
    unordered_map<string, int> mapping;
    mapping["acid"] = 0;
    mapping["alkali"] = 0;
    
    for(int i =0; i<n; i++){
        if(arr[i] < 0){ //put in acidArr
            acidArr[acidCount] = arr[i];
            acidCount++;
        }else if (arr[i] > 0){
            alkaliArr[alkaliCount] = arr[i];
            alkaliCount++;
        }
    }

    int initDiff = 0xffff;
    for(int acidJ = 0; acidArr[acidJ] != -1; acidJ++){
        for(int alkaliJ = 0; alkaliArr[alkaliJ] != -1; alkaliJ++){
            int diff = (acidArr[acidJ] + alkaliArr[alkaliJ]) - 0;
            if(abs(diff) < abs(initDiff)){
                initDiff = diff;
                mapping["acid"] = acidArr[acidJ];
                mapping["alkali"] = alkaliArr[alkaliJ];
            }
        }
    }
    
    return mapping;
}