백준 17608(막대기) c++

문제

17608번: 막대기

왼쪽부터 길이가 다른 막대를 세워두고. 막대들을 오른쪽에서 봤을때, 보이는 막대의 개수를 세는 문제입니다.

코드를 보겠습니다.

---

int n;
cin >> n;
stack<int>s;
for (int i = 0; i < n; i++) {
	int a;
	cin >> a;
	s.push(a);
}

먼저 막대의 개수 n을 입력받습니다.

막대 길이를 저장할 공간으로 stack을 선택했는데

막대가 왼쪽부터 오른쪽으로 세우므로 stack을 이용해 맨 아래부분(맨 왼쪽) 부터 맨 윗부분(맨 오른쪽) 으로 설정해두어

stack에 맨위에 있는 막대의 길이보다 그 밑의 길이가 크면 오른쪽에서 봤을때, 보입니다.

반대로 stack 맨위에 있는 막대의 길이보다 그 밑의 길이가 작으면 오른쪽에서 봤을때 보이지 않습니다.

이러한 원리를 이용하고자 stack 자료구조를 사용했습니다.

for문을 이용해 n개의 막대의 길이를 stack자료구조에 넣어둡니다.

int cnt = 1;
int t = s.top();
s.pop();
while (!s.empty()) {
	if (s.top() > t) {
		cnt++;
		t = s.top();
	}
	s.pop();
	
}
cout << cnt;

변수 cnt는 오른쪽에서 보이는 막대의 개수를 세기위한 변수입니다.

맨 오른쪽에 있는 막대는 무조건 보이므로 cnt의 값은 1부터 시작합니다.

변수 t는 맨 위에 있는 막대의 길이를 나타냅니다. 이를 이용하여 바로 밑의 막대 길이와 비교를 할것입니다.

맨 오른쪽 막대는 무조건 보이므로 pop() 함수를 이용해 없애고 while 문으로 들어갑니다.

while문은 stack의 원소가 비워질때까지 반복합니다.

먼저 if문에서 현재 맨앞에 막대의 길이(s.top()) 와 지금은 pop()함수를 이용하여 없어진 바로 위에있었던 막대의 길이(t)와 비교를 하게 됩니다.

현재 맨 앞에 있는 막대의 길이가 전에 있었던 막대의 길이보다 클경우 오른쪽에서 봤을때, 보이므로 

cnt값을 1더해주고 t의 값을 갱신해 줍니다. 

그 다음 pop()함수를 이용해 계속 반복해 주면 됩니다.

마지막으로 cnt값을 출력해주면 오른쪽에서 보이는 막대의 개수가 나오게 됩니다.

---

전체 코드입니다.

#include<iostream>
#include<vector>
#include<stack>
using namespace std;
int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
	int n;
	cin >> n;
	stack<int>s;
	for (int i = 0; i < n; i++) {
		int a;
		cin >> a;
		s.push(a);
	}
	int cnt = 1;
	int t = s.top();
	s.pop();
	while (!s.empty()) {
		if (s.top() > t) {
			cnt++;
			t = s.top();
		}
		s.pop();
	
	}
	cout << cnt;



	return 0;
}