[Algorithm]Baekjoon 3649번 :: 로봇 프로젝트

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

 

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
#include <functional>
#include <sstream>
#include <memory.h>
#include <deque>
#include <set>
#include <unordered_set>
 
using namespace std;
 
 
 
int x, n;
int arr[1000001] = { 0 };
 
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    while (cin >> x >> n)
    {
        unordered_map<int, int> check;
 
        for (int i = 0; i < n; ++i)
        {
            cin >> arr[i];
            ++check[arr[i]];
        }
 
        sort(arr, arr + n);
        bool dangerCheck = true;
 
        x *= 10000000;
        
        for (int i = 0; i < n; ++i)
        {
            int first = arr[i];
            int second = x - first;
            
            if (first > second) break;
            if (first == second && check[first] > 1)
            {
                dangerCheck = false;
 
                printf("yes %d %d\n", first, second);
                break;
            }
 
            if (first != second && check[second])
            {
                dangerCheck = false;
                printf("yes %d %d\n", first, second);
                break;
            }
        }
 
        if (dangerCheck)
        {
            printf("danger\n");
        }
    }
}
 
 

 

바로 생각난것은 그냥 인풋으로들어온 숫자들을 맵으로 체크해서 바로 구하는 방법.

다만 메모리를 많이사용해야하고 생각보다 시간도 많이걸린다. 

자질구레한 검사도 해야하고, 결국 O(1)에 가까운 unordered_map의 참조이지만, 어쨌든 많이해서 그런가보다.

 

아래는 투포인터코드

 

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
#include <functional>
#include <sstream>
#include <memory.h>
#include <deque>
#include <set>
#include <unordered_set>
 
using namespace std;
 
 
 
int x, n;
int arr[1000001] = { 0 };
 
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    while (cin >> x >> n)
    {
        for (int i = 0; i < n; ++i)
        {
            cin >> arr[i];
        }
 
        sort(arr, arr + n);
        x *= 10000000;
        
        int left = 0;
        int right = n - 1;
        bool check = true;
 
        while (left < right)
        {
            if (arr[left] + arr[right] == x)
            {
                check = false;
                printf("yes %d %d\n", arr[left], arr[right]);
                break;
            }
 
            if (arr[left] + arr[right] > x)
            {
                --right;
            }
            else
            {
                ++left;
            }
        }
 
        if (check)
        {
            printf("danger\n");
        }
    }
}