youngmin.log

[ 장르 ] String && Stack
[ 문제 ]

• My Code

// 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열
// 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)
#include <iostream>
#include <string>
#include <stack>

using namespace std;

int main()
{
	cin.tie(NULL); cout.tie(NULL); ios_base::sync_with_stdio(false);
	int n;
	string str;		// 괄호 문자열
	stack<char> stack;		// 괄호문자열 받을 스택

	cin >> n;
	int i = 0,j;
	while (i < n)
	{
		cin >> str;
		if (str.length() % 2 != 0)	// 문자열받은 괄호의 수가 애초에 홀수개이면 VPS가 아님
			cout << "NO" << '\n'; // NO 출력
		else   // 괄호 수가 일단 맞으면 
		{
			for (j = 0; j < str.size(); j++)	// 문자열 수만큼 반복
			{
				if (str[j] == '(')		// 여는 괄호면 스택에 넣고
					stack.push('(');
				else
				{	// 닫는 괄호면 가장 안쪽 여는괄호 스택에서 pop, 짝꿍
					if (!stack.empty()) { stack.pop(); }	// 단, 스택에 여는 괄호가 있는경우만
					else { break; }	// 스택에 여는 괄호없는데, 현재 닫는 괄호가 들어왔다면 VPS가 아님
				}
			}
			if (j == str.size() && stack.size() == 0)	// 괄호문자열 끝까지 조회했고, 여는 괄호스택도 다 쓴거면
				cout << "YES" << '\n';	// VPS 맞음
			else
				cout << "NO" << '\n';	// 아니면 VPS 아님
		}
		while (!stack.empty())	// 한 차례마다 끝나면, 여는괄호 스택 비우기
			stack.pop();
		i++;
	}
	return 0;
}

[ CheckPoint ]

• 문제를 읽어보면 딱 "스택" 문제라는걸 느낄 수 있을 것이다.
• 내 풀이 Point는 아래 부분이다.
  

• 문자열 끝까지 탐색을 했고, 그 때 여는 괄호 스택도 비어있을경우( 전부 사용한 경우 ) => VPS 가 맞음
  문자열 끝까지 탐색은 했는데, 여는 괄호 스택에 아직 데이터가 있는 경우( 여는 괄호가 남아있는 경우 ) => VPS 가 아님

• [ 장르 ] Heap or ★ Priority_queue
• [ 문제 ]

• My Code ( 최소 순차 힙(순차리스트,배열) 구현 ver. )

#include <iostream>
using namespace std;
int arr[100000], n = 0;

void insertItem(int data);
int removeMin();
void upHeap(int idx);
void downHeap(int idx);

int main()
{
	int N,data;

	cin.tie(NULL); cout.tie(NULL); ios_base::sync_with_stdio(false);
	cin >> N;
	while (N)
	{
		cin >> data;
		if (data != 0)
			insertItem(data);
		else
			if (data == 0 && n == 0)
				cout << 0 << '\n';
			else
				cout << removeMin() << '\n';
		N--;
	}
}
void insertItem(int data)
{
	arr[n + 1] = data;
	upHeap(n + 1);
	n = n + 1;
}
int removeMin()
{
	int removeData = arr[1];

	arr[1] = arr[n];
	downHeap(1);
	n = n - 1;
	return removeData;
}
void upHeap(int idx)
{
	int tmp;
	if (idx != 1)
	{
		if (arr[idx / 2] > arr[idx])
		{
			tmp = arr[idx];
			arr[idx] = arr[idx / 2];
			arr[idx / 2] = tmp;
			upHeap(idx / 2);
		}
	}
}
void downHeap(int idx)
{
	int smaller,tmp;
	
	if (n >= idx * 2)
	{
		smaller = idx * 2;
		if (n >= idx * 2 + 1)
			if (arr[smaller] > arr[idx * 2 + 1])
				smaller = idx * 2 + 1;
		if (arr[smaller] < arr[idx])
		{
			tmp = arr[idx];
			arr[idx] = arr[smaller];
			arr[smaller] = tmp;
			downHeap(smaller);
		}
	}
}

• ★ My Code ( Priority_queue < greater > ver. )

#include <iostream>
#include <queue>

using namespace std;

int main()
{
	int N, data;
	priority_queue<int, vector<int>, greater<int>> pq;		// ★ 내림차순 ( 기본옵션은 

	cin.tie(NULL); cout.tie(NULL); ios_base::sync_with_stdio(false);
	cin >> N;
	while (N)
	{
		cin >> data;
		if (data != 0)
			pq.push(data);
		else
			if (data == 0 && pq.size() == 0)
				cout << 0 << '\n';
			else
			{
				cout << pq.top() << '\n';
				pq.pop();
			}
		N--;
	}
}

• [ CheckPoint ]

• 먼저, 힙 생성에 대해서, 힙 생성은 1. 삽입식 힙생성, 2.상향식 힙생성이 있다.
  1. 삽입식 힙생성 : 힙에 value에 대한 정보가 순차적으로 제시되는 경우
  2. 상향식 힙생성 : 힙에 value가 한번에 제시되는 경우
• 이 문제는 그 중 삽입식 힙 생성이고, 최대 힙, 최소 힙중에 "최소 힙" 생성이다.
• 참고로, 힙은 순차힙( 배열에 의한 )과 연결 힙( 연결리스트에 의한 )이 있는데, 구현의 편의성을 위해 "순차 힙"으로 구현했다.
  ( 사실, 현재 이 글을 작성하는 시점에서의 힙을 나는 순차힙으로만 구현해 봐서, 순차 힙으로 구현했다..^^;; )
• ver.1 ( 구현한 힙 )은 기본적인 힙 생성 절차이기 때문에 천천히 코드를 읽어보면 이해가 될 것이다.
  
• 포인트는 ver.2 ( Priority_queue )로 구현한 것인데, 중요한 걸 먼저 짚고가면, 정확히 이것은 힙이 아니다 !
  힙에 대한 성질은 내부적으로보면 전혀 맞지 않고, 오로지 이 문제가 "최소 힙"이지만 결론적으로, 출력할 때 힙의 최소값만 출력하면 되는 방식이기 때문에, 내부적으로 어떤지는 중요하지 않다. ( 다시한번, 강조하지만 이 문제에만 초점을 맞췄다. )
• 다음은, 어찌 됬든 Priority_queue를 사용할 것을 알았다면, C++에서 Priority_queue에 대한 사용법을 알아야 한다.
  
• 헤더파일 : include <queue>
  선언시 : priority_queue<자료형, 구현체, 비교연산자>
  ex) priority_queue< int , vector<int> , greater<int> > pq  >>> 작은순서( top( ) 기준 오름차순 )
       priority_queue< int , vector<int> , less<int> > pq  >>> 큰 순서( top( ) 기준 내림차순 )
  이 부분을 알고가자.

• [ 장르 ] 탐색
• [ 문제 ]

• My Code

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;
int main()
{
	int N,M,data;
	vector<int> arr, check;
	
	cin.tie(NULL); cout.tie(NULL); ios_base::sync_with_stdio(false);

	cin >> N;
	for (int i = 0; i < N; i++)
	{
		cin >> data;
		arr.push_back(data);
	}
	cin >> M;
	for (int i = 0; i < M; i++)
	{
		cin >> data;
		check.push_back(data);
	}
	//sort(arr.begin(), arr.end());   // 처음엔 두 벡테를 정렬해놓고
	//sort(check.begin(), check.end());	// 비교하는 과정을 손볼려했는데 생각해보면 출력할 때 순서가 맞지 않는거 처럼 나온다.
	for (int i = 0; i < check.size(); i++)
	{
		auto iter = find(arr.begin(), arr.end(), check[i]);
		if (iter == arr.end()) 
			cout << 0 << '\n';
		else  
			cout << 1 << '\n';
	}
	return 0;
}

• CheckPoint

• 정답률이 낮아서, 성능을 높이는 문제인가하고 겁을 먹었다.
  그래서 일단 C++에 대한 입출력 성능을 높이기 위해 상단부에 선언을 해주고 개행도 '\n'으로 처리했다.
  
• 문제 포인트는 첫번째 받은 리스트안에 두번째 받은 리스트의 정수가 있는지 "들어온 순서대로" 체크해서 있으면 '1' 아니면 '0'을 출력하는 문제이다.
• 처음에는 뭔가 무작위로 들어오니 sort( )함수로 정렬 시킨 후 조건을 조작하면 최소한으로 탐색하지 않을까 했는데, 생각은 좋으나 이렇게하면 결과를 출력할 때, 기존의 리스트 순서가 바뀌어서 결과순서도 바뀌게 된다.
• 그래서 sort( )부분만 주석처리하고 제출했더니 정답이었다.
• 무엇보다 이 과정에서 check 벡터( 리스트로 생각하고 씀 )요소마다 arr 벡터( 리스트로 생각하고 씀 )내부에 존재하는지 for문을 통해 작성을 할 수도 있지만, find( )함수가 생각이나서 활용했다.
• ★ find( iter.begin( ), iter.end( ), 찾을 원소 ) 함수는 찾을 원소를 기준으로 iterator에 끝까지 조사해서 존재하면 그 위치의 iter를 반환하고 끝까지 조사했는데 찾을 원소가 없으면 v.end( ) (== 이것도 iterator ) 를 리턴한다. 이를 이용해서 if 문을 작성해서 처리했다.   

• [ 장르 ] deque
• [ 문제 ]

• My Code

#include <iostream>
#include <vector>
#include <deque>
#include <algorithm>

using namespace std;
int main()
{
	int queSize, selectCnt,want,answer = 0;
	deque<int> dq;
	vector<int> element;

	cin >> queSize >> selectCnt;
	for (int i = 0; i < queSize; i++)
		dq.push_back(i + 1);

	for (int i = 0; i < selectCnt; i++)
	{
		cin >> want;
		element.push_back(want);
	}

	for (int i = 0; i < selectCnt; i++)
	{
		
		if (element[i] == dq.front())
			dq.pop_front();
		else
		{
			int index = find(dq.begin(), dq.end(), element[i]) - dq.begin();	// ★
			if (index <= dq.size() - index)
			{
			//	cout << index << endl;
				while (dq.front() != element[i])
				{
					dq.push_back(dq.front());
					dq.pop_front();
					answer++;
				}
			}
			else
			{
			//	cout << index << endl;
				while (dq.front() != element[i])
				{
					dq.push_front(dq.back());
					dq.pop_back();
					answer++;
				}
			}
			dq.pop_front();
		}
		//for (auto iter = dq.begin(); iter != dq.end(); iter++)
			//cout << *iter << ' ';
		//cout << endl;
	}
	cout << answer << endl;
	return 0;
}

• [ CheckPoint ]

• 처음에는 문제가 어떤 걸 원하는지 제대로 이해를 못했다. 문제가 "회전하는 큐"라서 원형 큐를 쓰면 되는 건가 생각했다.
  
• 이 문제가 묻는 것은 원소의 값이 무엇인지는 상관없다. 단지 처음 큐에서 2번째 줄에 입력되는 원소의 위치 순서에 대해 우선순위를 주고
  이 우선순위에 따라서 첫번째 원소를 뽑아내는 과정에서 왼쪽 오른쪽 이동 연산을 몇번하는지 Count하는게 문제이다.
  이렇게 말해놓고 나도 뭔소린지 이해 못한다. 그냥 이 첨부자료를 보는 것이 좋겠다.
  
• 문제가 어느정도 이해가 가면, 이건 맨 앞에 요소를 뽑아 낼 때만, Count가 누적이 안되고, queue의 범위가 줄어들기 때문에 queue에서
  매 차례 원하는 원소를 뒤에서든 앞에서든 이동시킬수 있도록 deque를 써야한다는 것을 인지하게 될 것이다.
• 그 다음 포인트는, 문제를 풀다보면, 매 차례 왼쪽(front) 과 오른쪽(back) 방향 중 어느쪽으로 이번 차례에는 pop()을하면서 front로 정답 요소를 이동시켜야 할까이다.
  이것은 문제의 이동연산의 최솟값을 출력하라고 했으니, 매 시점의 deque에서 원하는 원소의 index위치를 구하고 이를 front와 back중에 더 가까운 쪽으로 pop( )하면서 이동하면 된다.
  단, 어찌됬든 원하는 원소는 결국 front에서 pop( )되기 때문에 back 방향으로 pop 을하면서 front로 보낼때는 이동연산을 한번 더 해야하는 것을 알아야한다.
• 결국 우리는 매 과정에서 변화하는 기존에 원소값 인덱스를 찾아야한다. 그렇기 때문에 나는 find( )연산자를 생각했다.
• [ 형식 ]
  find( iterator.begin( ), iterator.end( ), 찾길 원하는 원소 값 ) 
  [ 반환 값 ]
  원소의 위치에 iterator를 반환 !
• 결국 현재 내가 원하는 원소의 "인덱스"를 알고 싶다면, 리턴된 값 - 전체 iterator.begin( )을 해줘야 연산 결과가 인덱스 값이 된다.
  ( 코드의 ★ 부분 참고하길 바란다. )
• 그리고 이 인덱스 값은 0부터가 아닌 1부터임을 알자.

• [ 장르 ] Deque
• [ 문제 ]

• My Code

#include <iostream>
#include <deque>

using namespace std;
int main()
{
	cin.tie(NULL); cout.tie(NULL); ios_base::sync_with_stdio(false);
	int opcnt,i = 0,data;
	string str;
	deque<int> que;
	
	cin >> opcnt;
	while (i < opcnt)
	{
		cin >> str;
		if (!str.compare("push_back"))
		{
			cin >> data;
			que.push_back(data);
		}
		else if (!str.compare("push_front"))
		{
			cin >> data;
			que.push_front(data);
		}
		else if (!str.compare("front"))
		{
			if (que.empty()) cout << -1 << '\n';
			else cout << que.front() << '\n';
		}
		else if (!str.compare("back"))
		{
			if (que.empty()) cout << -1 << '\n';
			else cout << que.back() << '\n';
		}
		else if (!str.compare("pop_front"))
		{
			if (que.empty()) cout << -1 << '\n';
			else
			{
				cout << que.front() << '\n';
				que.pop_front();
			}
		}
		else if (!str.compare("pop_back"))
		{
			if (que.empty()) cout << -1 << '\n';
			else
			{
				cout << que.back() << '\n';
				que.pop_back();
			}
		}
		else if (!str.compare("size"))
			cout << que.size() << '\n';
		else
			cout << que.empty() << '\n';
		i++;
	}
	return 0;
}

[ CheckPoint ]

• 기본적인 Deque기능문제이다. C++은 Deque Container가 있기 때문에 deque연산을 쉽게 할 수 있다.
• Deque는 일반 queue와 달리 queue는 FIFO( First In First Out )으로
  들어가고 나가는 방향이 하나로, 보통 front, rear(back)으로 연산을 진행한다. 먼저 들어간 정보가 나올때도 가장 먼저 나간다.
• Deque는 들어가고 나가는 방향이 양방향이다. front,back 두 방향에서
  연산이 가능하다. 

• [ 장르 ] 재귀함수
• [ 문제 ]

• My Code

#include <iostream>
using namespace std;

void HanoiCount(int n);
void Hanoiprint(int start, int from, int end, int n);
int main()
{
	cin.tie(NULL); cout.tie(NULL); ios_base::sync_with_stdio(false);
	int num;
	cin >> num;
	HanoiCount(num);
	Hanoiprint(1, 2, 3, num);
	return 0;
}
void HanoiCount(int n)	// 하노이 탑 과정 수는 N개의 원반 수에 대해 (2^N -1)번
{
	int Pow = 1;
	for (int i = 0; i < n; i++)
		Pow *= 2;
	cout << Pow - 1 << '\n';
}
void Hanoiprint(int start, int from, int end, int n)
{
	if (n == 1)
		cout << start << ' ' << end << '\n';	// 기둥에 원반이 하나 남았을 경우
	else
	{
		Hanoiprint(start,end,from,n - 1);	// 그렇지 않으면 기둥의 마지막을 제외한 n-1개의 원반을 가운데 기둥에 옮기고
		cout << start << ' ' << end << '\n';	// 하나남은거 옮기고
		Hanoiprint(from, start, end, n - 1);	// 가운데 옮겼던 나머지기둥 목적지 기둥에 옮김
	}
}

• [ CheckPoint ]
  

1. 재귀함수의 대표적인 문제 중 하나인 하노이탑 문제이다. 하노이 탑의 성립 조건은 3개의 기둥 ( A,B,C ) 이라고 치자.
   A기둥의 크기가 다른 N개의 원반이 크기가 큰 순으로 쌓여있다. 목표는 C 기둥에 처음 상태 그대로 원반을 옮기는 것이다.
   
2. 주의사항은, 하노이탑의 원반들은 자기보다 큰 원반을 위에 쌓지 못한다. 그리고 한번에 한개의 원반만 옮길 수 있다.
3. N개의 원반을 하노이탑을 통해 처리하면, 항상 총 실행횟수는 (2^N - 1) 회 실행하게 된다.
4. 재귀함수 성질을 이용하는 것이 포인트인 문제. 재귀는 쉽게 생각할수록 좋다. 뭔가 반복적인 일을 수행할 때, 가장 작은 일의 단위인Base Case만 잘 생각하고, 나머지 많은 작업들은 또 다시 재귀를 통해 해결한다는 생각으로 코드를 작성하면 해결된다.
5. 이 문제 역시 로직을 잘 짜도, C++로 풀 경우 출력실행시간때문에 시간초과가 발생하기 떄문에, 코드 도입부에 C++입출력 개선코드를 삽입하고 개행도 endl보다 '\n'을 사용하면 해결 된다.
   
   

• [ 장르 ] Queue
• [ 문제 ]

• My Code

#include <iostream>
#include <queue>
#include <string>
using namespace std;

int main()
{
	int cnt,i = 0,data;
	queue<int> que;
	string str;

	cin.tie(NULL); cout.tie(NULL); ios_base::sync_with_stdio(false);	 // ★ 입출력속도개선선언부
	cin >> cnt;
	while (i < cnt)
	{
		cin >> str;
		if (!str.compare("push"))
		{
			cin >> data;
			que.push(data);
		}
		else if (!str.compare("pop"))
		{
			if (!que.empty())
			{
				cout << que.front() << '\n';	// ★ 개행마다 endl이 아닌 '\n'
				que.pop();
			}
			else
				cout << -1 << '\n';
		}
		else if (!str.compare("front"))
		{
			if (!que.empty())
				cout << que.front() << '\n';
			else
				cout << -1 << '\n';
		}
		else if (!str.compare("back"))
		{
			if (!que.empty())
				cout << que.back() << '\n';
			else
				cout << -1 << '\n';
		}
		else if (!str.compare("size"))
			cout << que.size() << '\n';
		else
			cout << que.empty() << '\n';
		i++;
	}
}

[ CheckPoint ]

• 기본적인 큐(Queue) 기능문제이다. C++에선 <queue> container에 모든 왠만한 queue연산은 제공되 있으므로 이를 잘 인지하고 있는지
  확인하는 정도의 문제이다.
• 다만, 이 문제 역시 실행속도 문제때문에 메인 본문에 코드에 주석처리로 된 ★ 부분이 선언부를 작성해주고, 하나 더 C++의 endl개행보다 
  '\n'  을 사용하는것을 지향한다.

• [ 장르 ] 트리

• My Code ( 트리생성 및 순회를 구현 )

#include <iostream>
using namespace std;

typedef struct Node
{
	char data;
	struct Node* left;
	struct Node* right;
}Node;

void MakeTree(Node* root,int n);
void MakeSubTree(Node* node, char MyData, char LData, char RData);
int IsInternal(Node* node);
void PreOrderPrint(Node *node);
void InOrderPrint(Node* node);
void PostOrderPrint(Node* node);

int main()
{
	Node root;
	int Nodecount;

	cin >> Nodecount;
	MakeTree(&root, Nodecount);
	return 0;
}
void MakeTree(Node* root,int n)
{
	char MyData, LData, RData;
	int i = 0;
	root->left = NULL;
	root->right = NULL;
	
	cin >> MyData >> LData >> RData;
	root->data = MyData;
	if (LData != '.')
	{
		Node *newNode = (Node*)malloc(sizeof(Node));
		newNode->data = LData;
		newNode->left = NULL;
		newNode->right = NULL;
		root->left = newNode;
	}
	if (RData != '.')
	{
		Node* newNode = (Node*)malloc(sizeof(Node));
		newNode->data = RData;
		newNode->left = NULL;
		newNode->right = NULL;
		root->right = newNode;
	}
	while (i < n - 1)
	{
		cin >> MyData >> LData >> RData;
		MakeSubTree(root, MyData, LData, RData);
		i++;
	}
	PreOrderPrint(root); cout << endl;
	InOrderPrint(root); cout << endl;
	PostOrderPrint(root); cout << endl;
}
void MakeSubTree(Node* node, char MyData, char LData, char RData)
{
	if (node->data == MyData)
	{
		if (LData != '.')
		{
			Node* newNode = (Node*)malloc(sizeof(Node));
			newNode->data = LData;
			newNode->left = NULL;
			newNode->right = NULL;
			node->left = newNode;
		}
		if (RData != '.')
		{
			Node* newNode = (Node*)malloc(sizeof(Node));
			newNode->data = RData;
			newNode->left = NULL;
			newNode->right = NULL;
			node->right = newNode;
		}
	}
	else
	{
		if (!(IsInternal(node)))
		{
			if (node->left != NULL)
				MakeSubTree(node->left, MyData, LData, RData);
			if (node->right != NULL)
				MakeSubTree(node->right, MyData, LData, RData);
		}
	}
}
int IsInternal(Node* node)
{
	return (node->left == NULL) && (node->right == NULL);
}
void PreOrderPrint(Node* node)
{
	cout << node->data;
	if (node->left != NULL)
		PreOrderPrint(node->left);
	if (node->right != NULL)
		PreOrderPrint(node->right);
}
void InOrderPrint(Node* node)
{
	if (node->left != NULL)
		InOrderPrint(node->left);
	cout << node->data;
	if (node->right != NULL)
		InOrderPrint(node->right);
}
void PostOrderPrint(Node* node)
{
	if (node->left != NULL)
		PostOrderPrint(node->left);
	if (node->right != NULL)
		PostOrderPrint(node->right);
	cout << node->data;
}

• Another Code ( 문제의 취지에 맞는 순차리스트(배열)을 이용한 풀이 )

#include <cstdio>

char tree[26][2] = { '.', };

void preorder(char root) {
    if (root == '.') return;
    else {
        printf("%c", root);
        preorder(tree[root-'A'][0]);
        preorder(tree[root-'A'][1]);
    }
}

void inorder(char root) {
    if (root == '.') return;
    else {
        inorder(tree[root-'A'][0]);
        printf("%c", root);
        inorder(tree[root-'A'][1]);
    }
}

void postorder(char root) {
    if (root == '.') return;
    else {
        postorder(tree[root-'A'][0]);
        postorder(tree[root-'A'][1]);
        printf("%c", root);
    }
}

int main() {

    int n, i;
    char root, left, right;

    scanf("%d", &n);

    for (i = 0; i < n; i++) {
        scanf(" %c %c %c", &root, &left, &right);
        tree[root-'A'][0] = left;		// [][0] => 왼쪽자식 
        tree[root-'A'][1] = right;		// [][1] => 오른쪽자식을 의미
    }

    preorder('A');
    printf("\n");
    inorder('A');
    printf("\n");
    postorder('A');
    printf("\n");

    return 0;
}

[ CheckPoint ]

• 기본적인 트리의 생성 및 순회 문제였기 때문에 특이사항은 없다.
• 다만, C++로 풀이함에 있어서 C++의 강점인 STL에는 Tree Containner는 없다는 점에서 좀 더 간단한 트리조작 방법이 없는지 아쉬웠다.
• 다른 사람의 참고할 코드에선 배열을 통한 풀이를 했다.
  알파벳 대문자는 26개이고, 노드의 정보가 들어가있지 않음을 의미하는 '.'의 대한 정보만을 이용했다. 26 X 2 2차원 배열이고 0번 인덱스는
  왼쪽자식, 1번 인덱스는 오른쪽자식을 의미, 노드의 정보는 알파벳 순으로 입력됨을 이용했다.

• [ 장르 ] Heap 또는 Priority_queue
• [ 문제 ]

• Code 1 ( 힙 을 구현한 ver. )

#include <iostream>
#include <vector>

using namespace std;
vector<int> arr;
int n = 0;

void downHeap(int idx)
{
	int greater, tmp;
	if (idx * 2 <= arr.size()-1)
	{
		greater = idx * 2;
		if (idx * 2 + 1 <= arr.size()-1)
			if (arr[greater] < arr[idx * 2 + 1])
				greater = idx * 2 + 1;
		if (arr[greater] > arr[idx])
		{
			tmp = arr[idx];
			arr[idx] = arr[greater];
			arr[greater] = tmp;
			downHeap(greater);
		}
	}
}
void upHeap(int idx)
{
	int max;
	if (idx / 2 >= 1)
	{
		if (arr[idx] > arr[idx / 2])
		{
			max = arr[idx];
			arr[idx] = arr[idx / 2];
			arr[idx / 2] = max;
			upHeap(idx / 2);
		}
	}
}
void InsertItem(int data)
{
	arr.push_back(data);
	upHeap(arr.size()-1);
	//n = n + 1;
}
int removeMax()
{
	if (arr.size() >= 2)
	{
		int rootValue = arr[1];

		arr[1] = arr.back();
		arr.pop_back();
		downHeap(1);
		//n = n - 1;

		return rootValue;
	}
}

int main()
{
  	cin.tie(NULL); cout.tie(NULL); ios_base::sync_with_stdio(false);	// ★ C++의 입출력속도개선의 매우중요
	int opcnt,X;
	arr.push_back(0);
	cin >> opcnt;
	for (int i = 0; i < opcnt; i++)
	{
		cin >> X;
		if (X == 0)
		{
			if (arr.size() == 1)
				cout << 0 << '\n';	// ★ 개행도 endl이 아닌 '\n'을 쓸 것
			else
				cout << removeMax() << '\n';
		}
		else
			InsertItem(X);
	}
	return 0;
}

• Code 2 ( Priority_queue를 활용한 ver. ( 정확히는 힙은 아닌 것 같다. )

#include <iostream>
#include <queue>

using namespace std;
int main()
{
	cin.tie(NULL); cout.tie(NULL); ios_base::sync_with_stdio(false);
	priority_queue<int> q;		// 우선순위 큐 ( FIFO,First In First Out )
	int opcnt,X;

	cin >> opcnt;
	for (int i = 0; i < opcnt; i++)
	{
		cin >> X;
		if (X == 0)
		{
			if (q.empty())
				cout << 0 << '\n';
			else
			{
				cout << q.top() << '\n';	// 우선순위 큐의 front 요소출력
				q.pop();	// front요소 pop
			}
		}
		else
			q.push(X);	// 우선순위 큐는 push하면서 자동으로 front에서부터 내림차순정렬
	}
	return 0;
}

[ CheckPoint ]

• 문제는 간단하다고 생각했으나 풀면서, 생각보다 몰랐던 부분, 생각해야 할 부분이 많았던 문제였다.
• 먼저, 최근에 나는 Heap에 대한 이론을 깨우쳐서 이 문제를 처음에는 힙을 만드는 과정의 삽입,삭제를 일일히 구현해서 메인에서 사용했다.
• 근데 생각해보니, 이 문제만 봤을 떈, 결국 삽입시에는 상관없고, 삭제하면서 출력시에 최대 값만 출력하면 되는 문제였다보니, 꼭 힙을 써야할까 ?
  생각이 들었다. 결론은 그러지 않아도 된다 !
• C++로 알고리즘 풀면서 이번에 queue container에 priority_queue를 쓰면
  매우 유용한 부분이 또 있다는 것을 알았다.
• 이는, queue와 기본적으로 FIFO형태라 보면 되는데, 특이점은 요소를 삽입시, default옵션이 자동으로 내림차순으로 PQ안에 요소들이 정렬된다는 것!
  문제에선 삭제시, 배열 내에 최대값을 삭제하면서 출력하는 것이 었으니
  queue.top( )을 통해서 큐에 front에 요소를 top( )하고, 후에 pop( )을하면 간단했다.
• 그리고, 무엇보다 이번에 가장 중요한 포인트는, 입출력과 관련된 시간이었다. 로직은 분명히 맞다. 맞는데. 이상하게 계속 시간초과가 뜬다. 이래저래 수를 써봤는데 변화가 없었다. 그러던 차에 구글링을 했더니 중요한 사항을 발견했다.

1. 글의 내용에서, C++기준으로 정리를 하자면, 입출력을 할때, 조금이라도 더 빠른 실행시간이 필요하다면, C++의 입출력인 cin,cout에 대해서
   cin.tie(NULL) , cout.tie(NULL) , ios_base::sync_with_stdio(false) 를 메인 문두에 선언
2. C++에서 개행 시에도 endl보다 '\n'을 사용하는 것이 속도적인 면에도 좋다.

그 외 백준알고리즘문제를 풀면서 참고해야 BOJ(Baekjoon) 참고사항 링크를 아래에 걸어둔다.
https://www.acmicpc.net/blog/view/55

• [ 장르 ] 스택

• Code 1 ( 입력 문자열 기능비교시 string.compare(string) 사용한 경우 ) 

// string.compare(string) 사용한 경우
#include <iostream>
#include <stack>
#include <string>
using namespace std;

int main()
{
	int cnt,data;
	stack<int> s;
	string str;
	//char str[5];
	cin >> cnt;
	
	for (int i = 0; i < cnt; i++)
	{
		cin >> str;
		//scanf("%s", str);
		if (str.compare("push") == 0)
		{
			cin >> data;
			s.push(data);
		}
		else if (str.compare("pop") == 0)
		{
			if (s.empty())
				cout << -1 << endl;
			else
			{
				cout << s.top() << endl;
				s.pop();
			}
		}
		else if (str.compare("top") == 0)
		{
			if (s.empty())
				cout << -1 << endl;
			else
				cout << s.top() << endl;
		}
		else if (str.compare("size") == 0)
			cout << s.size() << endl;
		else
		{
			if (s.empty())
				cout << 1 << endl;
			else
				cout << 0 << endl;
		}
	
	}
}

• Code 2 ( 입력 문자열 기능비교시 strcmp(string1,string2) 사용한 경우 )

// strcmp(string,string) 사용한 경우
#include <iostream>
#include <stack>
#include <string>
using namespace std;

int main()
{
	int cnt, data;
	stack<int> s;
	//string str;
	char str[5];
	cin >> cnt;

	for (int i = 0; i < cnt; i++)
	{
		//cin >> str;
		scanf("%s", str);
		if (strcmp(str,"push") == 0)
		{
			cin >> data;
			s.push(data);
		}
		else if (strcmp(str, "pop") == 0)
		{
			if (s.empty())
				cout << -1 << endl;
			else
			{
				cout << s.top() << endl;
				s.pop();
			}
		}
		else if (strcmp(str, "top") == 0)
		{
			if (s.empty())
				cout << -1 << endl;
			else
				cout << s.top() << endl;
		}
		else if (strcmp(str, "size") == 0)
			cout << s.size() << endl;
		else
		{
			if (s.empty())
				cout << 1 << endl;
			else
				cout << 0 << endl;
		}
	}
}

[ CheckPoint ]

• 일단, 문제는 말 그대로 스택에 기본적인 기능에 대해 구현하는 것이라서 어렵지 않다. 다만 pop이나 top을 할 때 항상 스택이 비어있는데 참조할려고 하지 않는지 empty를 통해서 사전에 방지해야한다.
  그렇지 않으면 런타임 에러가 발생한다.
• 그 외적으로, 문제를 풀면서 알게 된것은, 이 문제에서 스택에 기능을 영어 문자열로 입력을 받는데, 나는 최근까지 C언어를 많이 사용하다보니 문제가 쉬워보인다는 이유로 아무 생각없이 변수를 C++에있는 string변수로 선언하고 입력은 또 scanf( )로 받았다. 거기에 입력받은 문자는 각 "push","pop","top","size" 에 입력받은 문자열을 string container에 내장된 compare( ) 함수로 비교를 할려고 했다.
• 그러다 보니 아무리 제대로 문자열을 입력한 것 같아보여도, 결과적으론 문자열이 입력 받는거까진 좋은데, compare( ) 연산을하는데 이론상은 두 문자열이 같으면 0 을 반환하는 걸 이용해야하는게 그것이 적용이 안되는 것이다. 반대로 strcmp를 이용해 봤는데 이 역시 받아 들이질 않았다.
• 결론적으론, string변수를 쓴건 좋고, 그러면 입력과 출력을 C++의
  cout 와 cin만 이용을하거나, strcmp를 쓰면 char 형태의 배열을 선언해서 scanf printf를 만을 사용해서, scanf,printf 와 cin,cout 간의 두 입출력함수가 동시에 쓰이는 경우를 없애야한다.
• 이유는 혼동 되서 쓰이게 되면 싱크가 맞지 않아서 프로그램안에서 입력 순서가 바뀌는 참사가 발생한다고 한다.
  [ 참고자료 ]
  
  
• 추가적으로 프로그램 성능(실행시간)면에서 봤을 때, scanf,printf보다 cin,cout가 무거운 함수이다. 간단한 이유를 생각해보면, scanf,printf는 안에 형식들이 일일히 정해져서 들어가지만, cin,cout는 그냥 변수명만 넣기 때문에 컴파일러 내부적으로 이게 무슨 자료형이지 ? 등을 생각해야하기 때문에 당연히 속도적으로 느릴 수 밖에 없다.

저의 설명에 잘못됬거나 하는 것이 있다면 의견을 부탁드립니다.