[boj][c++] 10815 숫자카드, 10773 제로

utility 헤더 관련

이전에 스터디 진행하면서 utility 헤더 안 쓰고 pair쓰는 코드를 처음으로 봤는데 왜 가능한건지 의문이었다. 그런데 스터디 준비하며 관련 자료 찾아보니 utility헤더 안의 pair는 vector나 algorithm헤더 등에 포함돼있기 때문에 따로 헤더를 추가하지 않아도 된다고 한다. 알쓸신잡

10815 숫자 카드

이 문제는 집합과 맵 카테고리에 있는 문제였다. 주어진 숫자가 배열 안에 존재하는 숫자인지 확인하면 되는 간단한 문제였으나 제공되는 자료 범위가 천만 단위를 넘었기 때문에 이진탐색으로 풀었다.

• n개의 숫자를 arr배열에 넣고 내가 탐색할 m개의 숫자는 brr배열에 넣었다.
• arr배열을 오름차순 정렬한 뒤 brr배열 안의 값을 순서대로 이진탐색했다. 이진탐색은 반복문을 사용했다.

#include <iostream>
#include <algorithm>
using namespace std;

int arr[500001];
int brr[500001];

int main()
{
	int n, m;
	
	cin>>n;
	for(int i=0;i<n;i++)
	{
		cin>>arr[i];
	}
	sort(arr,arr+n);
	cin>>m;
	for(int i=0;i<m;i++)
	{
		cin>>brr[i];
	}
	for(int i=0;i<m;i++)
	{
		int start=0;
		int end=n-1;
		bool swc=false;
		while(start<=end)
		{
			int mid=(start+end)/2;
			if(arr[mid]==brr[i])
			{
				swc=true;
				break;
			}	
			else if(arr[mid]<brr[i])
				start=mid+1;
			else
				end=mid-1;
		}
		if(swc==false)
		{
			cout<<"0"<<" ";
		}
		else if(swc==true)
		{
			cout<<"1"<<" ";
		}
	}
}

---

10773 제로

스택 관련 문제였다. 스택이나 큐 관련된 문제는 deque로 푸는게 좋다고 들어서 해당 컨테이너 포함해서 풀었다. 실버2가 얼마 안 남아서 여러 문제 푸는 중이었는데 이게 solved 클래스에 속한 문제였던 모양이다. 이 문제 풀자마자 실버2로 올랐다.

#include <iostream>
#include <deque>
using namespace std;

int main()
{
	int n;
	deque<int> d;
	cin >> n;
	for(int i = 0;i < n;i++)
	{
		int a;
		cin >> a;
		if(a == 0)
		{
			if(!d.empty())
				d.pop_back();
		}
		else
		{
			d.push_back(a);	
		}
	}
	int sum=0;
	for(int i=0;i < d.size();i++)
	{
		sum += d[i];
	}
	cout<<sum<<endl;
}