백준 - 1836번 : 스카이라인 쉬운거 (C++)

풀이 방법
1. set을 이용한 풀이
2. stack을 이용한 풀이

처음엔 그냥 생각나는 대로 풀었다. 입력된 높이가 이전에 입력되지 않은 높이라면 건물로 인정이 될 수 있다. 하지만 입력된 적이 있는 높이라고 하더라도 그 사이에 자기보다 낮은 높이가 입력된 적이 있다면 이전의 입력과 구별되는 다른 건물로 확정될 수 있다.

set 컨테이너는 자가 균형 이진 탐색 트리로 구현되어 있으니 정렬 상태를 유지하면서 빠르게 현재 입력값을 추가하고 그를 초과하는 값을 제거하는 데에 적합할 것이라 생각하여 set을 선택했다.

입력이 들어오는 대로 set컨테이너를 탐색하여 입력된 적이 없을 경우 건물 갯수를 증가 시켜주고 set에 추가하고 이미 들어온 값들 중 현재 값을 초과하는 값들을 set에서 삭제해주었다.

set을 이용한 풀이

#include <iostream>
#include <set>

using namespace std;

int main()
{
	int N;
	cin >> N;

	int Answer = 0;
	set<int> setNum;

	for (int i = 0; i < N; ++i)
	{
		int x, y;
		cin >> x >> y;
		auto iter = setNum.find(y);
		auto iterEnd = setNum.end();

		if (iter == iterEnd) // 입력된 적이 없을 경우
		{
			if (y != 0)
			{
				++Answer;

				setNum.insert(y);
				iter = setNum.find(y);
				++iter;
			}

			else
				iter = setNum.begin();

		}

		else
			++iter;

		for (; iter != iterEnd;)
		{
			iter = setNum.erase(iter);
		}
	}

	cout << Answer;
}

근데 이렇게 풀고나서 분류를 보니 스택 문제로 분류되어있더라.
그래서 좀 더 생각해보니 결국에는 현재 값과 가장 나중에 들어온 값들을 비교해서 현재 입력 값이 더 작을 경우 건물의 카운트를 증가 시켜주면 될 것 같더라.

스택을 이용한 풀이

#include <iostream>
#include <stack>

using namespace std;

int main()
{
	int N;
	cin >> N;

	int Answer = 0;
	stack<int> sNum;

	for (int i = 0; i <= N; ++i)
	{
		int x, y;

		if(i != N)
			cin >> x >> y;

		else
			y = 0; // 모든 입력이 끝난 후에 스택에 남아있는 것들 정리하기 위함 
		
		while (!sNum.empty())
		{
			int Top = sNum.top();

			if (Top > y)
			{
				++Answer;
				sNum.pop();
			}

			else if (Top == y)
				sNum.pop();

			else
				break;

		}

		sNum.push(y);
	}

	cout << Answer;
}

스택으로 푸는게 코드도 더 간결하고 미세(?)하지만 메모리도 덜 쓴다. 근데 스택 문제는 항상 이게 스택문제인지 잘 파악하기 힘들다..
많이 풀어봐야겠다...